f



How to generate all permutations of a string?

Hi guys,
  I want to generate all permutations of a string. I've managed to
generate all cyclic permutations. Please help :)

def permute(string):
    l= []
    l.append(string)
    string1 = ''
    for i in range(0,len(string)-1,1):
        string1 = string[1:len(string)] + string[:1]
        l.append(string1)
        string = string1
    return l

0
girish1 (31)
6/22/2006 8:07:07 AM
comp.lang.python 77058 articles. 6 followers. Post Follow

11 Replies
33594 Views

Similar Articles

[PageSpeed] 25

In article <mailman.7352.1150963651.27775.python-list@python.org>,
 "Girish Sahani" <girish@cse.iitb.ac.in> wrote:

>  I want to generate all permutations of a string.

def permute(Seq) :
    """generator which yields successive permutations of the elements
    of Seq."""
    if len(Seq) == 0 :
        yield ()
    else :
        for i in range(0, len(Seq)) :
            for rest in permute(Seq[:i] + Seq[i + 1:]) :
                yield (Seq[i],) + rest
            #end for
        #end for
    #end if
#end permute
0
ldo (2177)
6/22/2006 8:47:50 AM
> In article <mailman.7352.1150963651.27775.python-list@python.org>,
>  "Girish Sahani" <girish@cse.iitb.ac.in> wrote:
>
>>  I want to generate all permutations of a string.
>
> def permute(Seq) :
>     """generator which yields successive permutations of the elements
>     of Seq."""
>     if len(Seq) == 0 :
>         yield ()
>     else :
>         for i in range(0, len(Seq)) :
>             for rest in permute(Seq[:i] + Seq[i + 1:]) :
>                 yield (Seq[i],) + rest
>             #end for
>         #end for
>     #end if
> #end permute
thanks lawrence...however this func doesnt return the permuted strings, so
i added some code as follows to generate a list of all the permutations:

def permute(seq):
    l = []
    if len(seq) == 0:
        yield []
    else:
        for i in range(0,len(seq)):
            for rest in permute(seq[:i] + seq[i+1:]):
                yield (seq[i],) + rest
    for t in permute(seq):
        l.append(''.join(t))
    return l

This gives me a syntax error!
I need to output a list that has all the permutations of the input string.



> --
> http://mail.python.org/mailman/listinfo/python-list
>

0
girish1 (31)
6/22/2006 9:35:39 AM
Mind, that Lawrence's solution may contain doubles:

>>> [ i for i in permute("aa") ]
[('a', 'a'), ('a', 'a')]

If you don't want this, use sets.

0
bayerj (17)
6/22/2006 9:39:43 AM
In article <mailman.7352.1150963651.27775.python-list@python.org>,
Girish Sahani <girish@cse.iitb.ac.in> wrote:
>Hi guys,
>  I want to generate all permutations of a string. I've managed to
>generate all cyclic permutations. Please help :)
>
>def permute(string):
>    l= []
>    l.append(string)
>    string1 = ''
>    for i in range(0,len(string)-1,1):
>        string1 = string[1:len(string)] + string[:1]
>        l.append(string1)
>        string = string1
>    return l
>

Those so passionate about enumerations as to consider *everything*
known about them, and not just a specific Python function, will
want to be aware of the referent of <URL:
http://www.unixreview.com/documents/s=10089/ur0606j/ur0606j.html >
and related materials.
and its referents.
0
claird (2363)
6/22/2006 10:42:07 AM
Girish Sahani wrote:

>   I want to generate all permutations of a string. I've managed to
> generate all cyclic permutations. Please help :)

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496724

anton
0
6/22/2006 1:58:04 PM
Girish Sahani wrote:
> Hi guys,
>   I want to generate all permutations of a string. I've managed to
> generate all cyclic permutations. Please help :)
> 


http://gflanagan.net/site/python/05/Johnson.html


Gerard

0
grflanagan (262)
6/22/2006 2:33:37 PM
Girish Sahani wrote:
>>In article <mailman.7352.1150963651.27775.python-list@python.org>,
>> "Girish Sahani" <girish@cse.iitb.ac.in> wrote:
>>
>>
>>> I want to generate all permutations of a string.
>>
>>def permute(Seq) :
>>    """generator which yields successive permutations of the elements
>>    of Seq."""
>>    if len(Seq) == 0 :
>>        yield ()
>>    else :
>>        for i in range(0, len(Seq)) :
>>            for rest in permute(Seq[:i] + Seq[i + 1:]) :
>>                yield (Seq[i],) + rest
>>            #end for
>>        #end for
>>    #end if
>>#end permute
> 
> thanks lawrence...however this func doesnt return the permuted strings, so
> i added some code as follows to generate a list of all the permutations:
> 
> def permute(seq):
>     l = []
>     if len(seq) == 0:
>         yield []
>     else:
>         for i in range(0,len(seq)):
>             for rest in permute(seq[:i] + seq[i+1:]):
>                 yield (seq[i],) + rest
>     for t in permute(seq):
>         l.append(''.join(t))
>     return l
> 
> This gives me a syntax error!
> I need to output a list that has all the permutations of the input string.
> 
> 
> 
> 
>>--
>>http://mail.python.org/mailman/listinfo/python-list
>>
> 
> 

p = ["".join(s) for s in permute('abcdefg')]

-- 
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/
0
jstroud (199)
6/22/2006 5:56:44 PM
>> thanks lawrence...however this func doesnt return the permuted strings,
>> so
>> i added some code as follows to generate a list of all the permutations:
>>
>> def permute(seq):
>>     l = []
>>     if len(seq) == 0:
>>         yield []
>>     else:
>>         for i in range(0,len(seq)):
>>             for rest in permute(seq[:i] + seq[i+1:]):
>>                 yield (seq[i],) + rest
>>     for t in permute(seq):
>>         l.append(''.join(t))
>>     return l
>>
>> This gives me a syntax error!
>> I need to output a list that has all the permutations of the input
>> string.
>>
>>
>>
>>
>>>--
>>>http://mail.python.org/mailman/listinfo/python-list
>>>
>>
>>
>
> p = ["".join(s) for s in permute('abcdefg')]

This fails to work too. I'm trying to call permute func from another func,
python gives me a TypeError as follows:

def permute(seq):
    l = []
    if len(seq) == 0:
        yield []
    else:
        for i in range(0,len(seq)):
            for rest in permute(seq[:i] + seq[i+1:]):
                yield (seq[i],) + rest

def main(stringList):
    for string in stringList:
        permList = list(permute(string))
        l = ["".join(s) for s in permList]

>>> l = ['abc','abd','bcd']
>>> main(l)
TypeError: can only concatenate tuple (not "list") to tuple



>
> --
> James Stroud
> UCLA-DOE Institute for Genomics and Proteomics
> Box 951570
> Los Angeles, CA 90095
>
> http://www.jamesstroud.com/
> --
> http://mail.python.org/mailman/listinfo/python-list
>

0
girish1 (31)
6/23/2006 1:42:10 AM
Girish Sahani wrote:
>>>thanks lawrence...however this func doesnt return the permuted strings,
>>>so
>>>i added some code as follows to generate a list of all the permutations:
>>>
>>>def permute(seq):
>>>    l = []
>>>    if len(seq) == 0:
>>>        yield []
>>>    else:
>>>        for i in range(0,len(seq)):
>>>            for rest in permute(seq[:i] + seq[i+1:]):
>>>                yield (seq[i],) + rest
>>>    for t in permute(seq):
>>>        l.append(''.join(t))
>>>    return l
>>>
>>>This gives me a syntax error!
>>>I need to output a list that has all the permutations of the input
>>>string.
>>>
>>>
>>>
>>>
>>>
>>>>--
>>>>http://mail.python.org/mailman/listinfo/python-list
>>>>
>>>
>>>
>>p = ["".join(s) for s in permute('abcdefg')]
> 
> 
> This fails to work too. I'm trying to call permute func from another func,
> python gives me a TypeError as follows:
> 
> def permute(seq):
>     l = []
>     if len(seq) == 0:
>         yield []
>     else:
>         for i in range(0,len(seq)):
>             for rest in permute(seq[:i] + seq[i+1:]):
>                 yield (seq[i],) + rest
> 
> def main(stringList):
>     for string in stringList:
>         permList = list(permute(string))
>         l = ["".join(s) for s in permList]
> 
> 
>>>>l = ['abc','abd','bcd']
>>>>main(l)
> 
> TypeError: can only concatenate tuple (not "list") to tuple
> 

I think I should have provided a context for my example. It was to be 
used with Lawrence D'Olivero's code and not yours.

James

 >>> def permute(Seq) :
....     """generator which yields successive permutations of the elements
....     of Seq."""
....     if len(Seq) == 0 :
....         yield ()
....     else :
....         for i in range(0, len(Seq)) :
....             for rest in permute(Seq[:i] + Seq[i + 1:]) :
....                 yield (Seq[i],) + rest
....
 >>> def main(stringList):
....     for string in stringList:
....         l = ["".join(s) for s in permute(string)]
....         print l
....
 >>> l
['abc', 'abd', 'bcd']
 >>> main(l)
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
['abd', 'adb', 'bad', 'bda', 'dab', 'dba']
['bcd', 'bdc', 'cbd', 'cdb', 'dbc', 'dcb']

0
jstroud (199)
6/23/2006 4:56:38 AM
Another generator solution, based on computing a permutation from its rank 
according to some natural order. Written for strings.

def perms(s) :
     def nth(n,L,k=1) :
         if k>len(L) :
             if n :
                 raise StopIteration
             return ''
         return nth(n/k,L,k+1)+L.pop(n%k)
     for n in xrange(1<<30) :
         yield nth(n,list(s))
0
bborcic (208)
6/23/2006 6:16:14 PM
I wrote:
> Another generator solution, based on computing a permutation from its 
> rank according to some natural order. Written for strings.
> 
> def perms(s) :
>     def nth(n,L,k=1) :
>         if k>len(L) :
>             if n :
>                 raise StopIteration
>             return ''
>         return nth(n/k,L,k+1)+L.pop(n%k)
>     for n in xrange(1<<30) :
>         yield nth(n,list(s))

Same principle, simpler (no recursion, no helper func, less tokens, easier to 
read) :

def perms(s) :
     for n in xrange(1<<30) :
         R,L = [],list(s)
         while L :
             n,k = divmod(n,len(L))
             R.append(L.pop(k))
         if n : break
         yield ''.join(R)

Or if you *really* prefer lisp-style recursions, here is the solution as a 
single lambda that returns a tuple of strings (not a generator as above)

perms = lambda *S : \
             (len(S)>=len(S[0]) and S[0]==S[-1]) \
             and S[min(1,len(S)-1):] \
             or perms(''.join(L.pop(k)
                              for n,L in [[len(S),list(S[-1])]]
                              for _ in S[0]
                              for n,k in [divmod(n,len(L))]
                              )
                      ,*S)
0
bborcic (208)
6/26/2006 6:16:50 PM
Reply: