Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!rex!ginosko!uunet!prcrs!mcvic
From: mcvic@prcrs.UUCP (David J. McVicar)
Newsgroups: comp.lang.c
Subject: Character String Permutation
Keywords: permutation
Message-ID: <193@prcrs.UUCP>
Date: 14 Sep 89 00:52:26 GMT
Organization: PRC Realty Systems, McLean, VA
Lines: 113


I have wrestled with this annoying algorithm long enough.  Can anyone
on the net lend assitance?

Here's what I'm trying to do...

I have written a small C program to list out all the permutations
of a given text string.

(ex. unix unxi uinx uixn uxni uxin nuix nuxi niux nixu nxui nxiu iunx iuxn inux 
     inxu ixun ixnu xuni xuin xnui xniu xiun xinu)

But, when a string containing repeating characters is entered, I would like
to output only unique strings.

(ex.  foo foo ofo oof ofo oof  <=  my current program
      foo ofo oof	       <=  desired output)


An obvious solution for UNIX types is to pipe the output into sort -u, but for 
long character strings this would be prohibitive.  Is there any way, given 
the nature of my solution below, to determine repeats in permutations on the 
fly?

Thanks in advance for any help with this one.

Dave McVicar (uunet!prcrs!mcvic)

======  The program below will print out all permutations, with repeats =====

#include <stdio.h>

#define  COLWID		80
extern char  *malloc();

int      *pa;
char     *str;
char     *outbuf;
int	  size;

int func()
{
	static int    col = 0;
	register int i;

	for(i=0; i < size; ++i)
		outbuf[i] = str[pa[i]];
	outbuf[i] = '\0';
	if ((col += (size + 1)) >= COLWID) {
		printf("\n");
		col = size + 1;
	}
	printf("%s ", outbuf);
	return (1);
} /* end func() subroutine */


int
doperm(offset, func)
register int offset;
int    (*func)();
{
	int               index;
	int               k, skip;

	if (offset == size)
		return( (*func)() );
	for (index = 0; index < size; ++index) {
		for (k = 0; k < offset; ++k)
			if (skip = (index == pa[k]))
				break;
		if (skip)
			continue;
		pa[offset] = index;
		doperm(offset + 1, func);
	}
	return;
}

main(argc, argv)
int 		argc;
char 	      **argv;
{
	register int i,j;

	if (argc == 1) {
		fprintf (stderr, "usage:  permute <string>\n\n");
		exit (2);
	}

	str = argv[1];
	size = strlen(str);
	if (size == 0)
		exit(0);
	else if (size == 1) {
		printf("%s\n", argv[1]);
		exit(0);
	}
	pa = (int *)malloc(size * sizeof(int));
	outbuf = malloc(size + 1);

	for (i = 0; i < size; ++i) {
		pa[0] = i;
                for (j = 1; j < size; ++j)
			pa[j] = 0;
	        doperm(1, func);
	}
	free(pa);
	free(outbuf);
	exit(0);
}

======================