Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ukma!uflorida!novavax!twwells!bill
From: bill@twwells.com (T. William Wells)
Newsgroups: comp.lang.c
Subject: Re: Character String Permutation
Keywords: permutation
Message-ID: <1989Sep14.184346.8361@twwells.com>
Date: 14 Sep 89 18:43:46 GMT
References: <193@prcrs.UUCP>
Organization: None, Ft. Lauderdale, FL
Lines: 56

In article <193@prcrs.UUCP> mcvic@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@twwells.com