Character String Permutation
Al Dunbar
userAKDU at ualtamts.BITNET
Tue Sep 19 00:09:17 AEST 1989
In article <1989Sep14.184346.8361 at twwells.com>, bill at twwells.com (T. William Wells) writes:
>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.
That would certainly work, but then David's unix --> xinu
example would become inux --> xuni. Perhaps he has a reason for
the resulting sequence to start with the original word and end
with it spelled in reverse. If this is the case, change your
comment to: ".. except that, when replacing a character on a
given level, if it is the same as any character already used for
that level, skip the character". This could easily be done by
strcat'ing each character to be used to an auto string variable,
but only if strchr'ing for it first indicates that it is not
there yet. The space required for this variable would decrease
by one for each level, requiring a total of ((size+1)*(size)/2)
bytes.
/Al Dunbar - Civil Eng. Univ of Alberta, CANADA
More information about the Comp.lang.c
mailing list