[Tutor] How to generate permutations of a given string

[Carroll, Barry]

Dick, et al:

> -----Original Message-----
> Date: Tue, 28 Nov 2006 12:57:51 -0800
> From: Dick Moores <rdm at rcblue.com>
> Subject: Re: [Tutor] How to generate permutations of a given string
> To: Python Tutor List <tutor at python.org>
> Message-ID: <7.0.1.0.2.20061128122720.075e9cc8 at rcblue.com>
> Content-Type: text/plain; charset="us-ascii"; format=flowed
> 
> At 02:49 PM 11/27/2006, John Fouhy wrote:
> >On 28/11/06, Carroll, Barry <Barry.Carroll at psc.com> wrote:
> > > I'm not sure these qualify as "simple", but they work.  This was
one
> of
> > > my very first projects in Python, so it may be more complicated
than
> > > necessary.
> >
> >This is an alternative approach:
> >http://mail.python.org/pipermail/tutor/2005-May/038059.html
> 
> However, this is not what someone looking for an anagram algorithm
> would find useful, it seems to me.
> 
> Barry Carroll offering does the job, if the last line is revised as
> shown below:
> 
> def permute(word):
>          """
>          By Barry Carrol <Barry.Carroll at psc.com>
>          on Tutor list, revised (last line) by me.
>          """
>          retList=[]
>          if len(word) == 1:
>                  # There is only one possible permutation
>                  retList.append(word)
>          else:
>                  # Return a list of all permutations using all
characters
>                  for pos in range(len(word)):
>                          # Get the permutations of the rest of the
word
> 
> permuteList=permute(word[0:pos]+word[pos+1:len(word)])
>                          # Now, tack the first char onto each word in
the
> list
>                          # and add it to the output
>                          for item in permuteList:
>                                  retList.append(word[pos]+item)
>          #return retList
>          return list(set(retList)) # make elements of retList unique
> 
> (The line in the code in Barry's post,
> "permuteList=permute2(word[0:pos]+word[pos+1:len(word)])", was
> corrected to "permuteList=permute(word[0:pos]+word[pos+1:len(word)])"
> in an email from him to me.)
> (i.e., permute2 changed to permute)
> 
> Dick Moores
In the intrest of reusability, I would recommend leaving permute as it
is and calling it from another function:

#####
>>>>> def permuteset(word):
>>>>>     return list(set(permute(word)))

>>>>> permute("121")
>>>>> ['121', '112', '211', '211', '112', '121']

>>>>> permuteset("121")
>>>>> ['121', '211', '112']
#####

If you're sure you will never want to use the permute function in any
other way, then it doesn't matter, of course.  Otherwise, it's nice to
have the original function intact, in case you ever want a list of all
the combinations that ARE duplicates, for example ;*)

FWIW.

Regards,

Barry