Velocity Reviews > How to generate all permutations of a string?

# How to generate all permutations of a string?

Girish Sahani
Guest
Posts: n/a

 06-22-2006
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

Lawrence D'Oliveiro
Guest
Posts: n/a

 06-22-2006
In article <(E-Mail Removed)>,
"Girish Sahani" <(E-Mail Removed)> 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

Girish Sahani
Guest
Posts: n/a

 06-22-2006
> In article <(E-Mail Removed)>,
> "Girish Sahani" <(E-Mail Removed)> 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
>

bayerj
Guest
Posts: n/a

 06-22-2006
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.

Cameron Laird
Guest
Posts: n/a

 06-22-2006
In article <(E-Mail Removed)>,
Girish Sahani <(E-Mail Removed)> 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/...j/ur0606j.html >
and related materials.
and its referents.

Anton Vredegoor
Guest
Posts: n/a

 06-22-2006
Girish Sahani wrote:

> I want to generate all permutations of a string. I've managed to

http://aspn.activestate.com/ASPN/Coo.../Recipe/496724

anton

Gerard Flanagan
Guest
Posts: n/a

 06-22-2006

Girish Sahani wrote:
> Hi guys,
> I want to generate all permutations of a string. I've managed to
>

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

Gerard

James Stroud
Guest
Posts: n/a

 06-22-2006
Girish Sahani wrote:
>>In article <(E-Mail Removed)>,
>> "Girish Sahani" <(E-Mail Removed)> 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/

Girish Sahani
Guest
Posts: n/a

 06-23-2006
>> 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
>

James Stroud
Guest
Posts: n/a

 06-23-2006
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']
['bcd', 'bdc', 'cbd', 'cdb', 'dbc', 'dcb']