# How to generate all permutations of a string?

Discussion in 'Python' started by Girish Sahani, Jun 22, 2006.

1. ### Girish SahaniGuest

Hi guys,
I want to generate all permutations of a string. I've managed to

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

Girish Sahani, Jun 22, 2006

2. ### Lawrence D'OliveiroGuest

In article <>,
"Girish Sahani" <> 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,) + rest
#end for
#end for
#end if
#end permute

Lawrence D'Oliveiro, Jun 22, 2006

3. ### Girish SahaniGuest

> In article <>,
> "Girish Sahani" <> 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,) + 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,) + 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.

Girish Sahani, Jun 22, 2006
4. ### bayerjGuest

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.

bayerj, Jun 22, 2006
5. ### Cameron LairdGuest

In article <>,
Girish Sahani <> wrote:
>Hi guys,
> I want to generate all permutations of a string. I've managed to
>
>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.

Cameron Laird, Jun 22, 2006
6. ### Anton VredegoorGuest

Anton Vredegoor, Jun 22, 2006
7. ### Gerard FlanaganGuest

Gerard Flanagan, Jun 22, 2006
8. ### James StroudGuest

Girish Sahani wrote:
>>In article <>,
>> "Girish Sahani" <> 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,) + 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,) + 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.
>
>
>
>
>
>

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/

James Stroud, Jun 22, 2006
9. ### Girish SahaniGuest

>> 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,) + 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.
>>
>>
>>
>>
>>
>>

>
> 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,) + 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
>

Girish Sahani, Jun 23, 2006
10. ### James StroudGuest

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,) + 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,) + 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,) + 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']
['bcd', 'bdc', 'cbd', 'cdb', 'dbc', 'dcb']

James Stroud, Jun 23, 2006
11. ### Boris BorcicGuest

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))

Boris Borcic, Jun 23, 2006
12. ### Boris BorcicGuest

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

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)

Boris Borcic, Jun 26, 2006