[Tutor] How to generate permutations of a given string

[Carroll, Barry]

Hello, Asrarahmed

> -----Original Message-----
> Date: Mon, 27 Nov 2006 12:06:54 +0000
> From: "Asrarahmed Kadri" <ajkadri at googlemail.com>
> Subject: [Tutor] How to generate permutations of a given string
> To: tutor-python <tutor at python.org>
> Message-ID:
> 	<b4e894c70611270406l266278f9pcd3de170de25dd99 at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> Hello folks,
> 
> 
> Can someone help me with a simple algorithm to generate permutations
of a
> given string:
> 
> Input string:---->> 'abc'
> 
> Output:------->>  ['abc','acb','bac','bca','cab','cba']
> 
> Thanks.
> Regards,
> Asrarahmed Kadri
> -
> To HIM you shall return.

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.  

##########
def permute (word):
"""
    Accepts a string. 
    Returns a list of all permutations of the string using all
characters.  
"""
    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=permute2(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
##########

Regards,
 
Barry
barry.carroll at psc.com
541-302-1107
________________________
We who cut mere stones must always be envisioning cathedrals.

-Quarry worker's creed