Character String Permutation

[T. William Wells]

In article <193 at prcrs.UUCP> mcvic at prcrs.UUCP (David J. McVicar) writes:
: 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)

Group identical characters of the input string together. Sorting them
will do nicely. Do the standard recursive generation of the
permutations, except that, when replacing a character on a given
level, if it is the same as the old character for that level, skip the
character.

Warning: never compiled C code follows. Not only that, but this naive
algorithm is O(Length**Length) rather than O(Length!). Fixing that is
left as an exercise for the student. :-)

char    Selected[MAX];          /* initially all zero */
char    Perm_vector[MAX+1];     /* bad name, my APL past is showing! */
char    Sorted_vector[MAX];     /* sorted alphabetically, nul not allowed */
int     Depth;                  /* initially zero */
int     Length;                 /* chars Sorted_vector, <= MAX */

void
generate()
{
	int     i;
	int     lastc;

	Perm_vector[Depth] = 0;
	if (Depth == Length) {
		puts(Perm_vector);
		return;
	}
	for (i = 0; i < Length; ++i) {
		if (Selected[i]
		    || Sorted_vector[i] == Perm_vector[Depth]) {
			continue;
		}
		Perm_vector[Depth] = Sorted_vector[i];
		++Depth;
		Selected[i] = 1;
		generate();
		Selected[i] = 0;
	}
}

---
Bill                    { uunet | novavax | ankh | sunvice } !twwells!bill
bill at twwells.com