How to generate all permutations of a string?

[Girish Sahani]

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

 

[Lawrence D'Oliveiro]

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

 

[Girish Sahani]

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.

 

[bayerj]

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]

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.

 

[Anton Vredegoor]

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

 

[Gerard Flanagan]

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

 

[James Stroud]

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/

 

[Girish Sahani]

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]

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

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
.... """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
........ 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']

 

[Boris Borcic]

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]

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)