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 6/22/2006 8:07:07 AM comp.lang.python  77058 articles. 6 followers. 11 Replies 33731 Views Similar Articles

[PageSpeed] 0

```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 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 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 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 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 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 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 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 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 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) and S==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
for n,k in [divmod(n,len(L))]
)
,*S)
``` 0 6/26/2006 6:16:50 PM
 Reply: