Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!ubc-cs!alberta!uqv-mts!Al_Dunbar
From: userAKDU@ualtamts.BITNET (Al Dunbar)
Newsgroups: comp.lang.c
Subject: Re: Character String Permutation
Message-ID: <347@ualtamts.BITNET>
Date: 18 Sep 89 14:09:17 GMT
References: <193@prcrs.UUCP> <1989Sep14.184346.8361@twwells.com>
Organization: University of Alberta (MTS)
Lines: 34

In article <1989Sep14.184346.8361@twwells.com>, bill@twwells.com (T. William Wells) writes:
>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.
 
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