473,320 Members | 1,978 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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

Jun 22 '06 #1
11 5873
In article <ma***************************************@python. org>,
"Girish Sahani" <gi****@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
Jun 22 '06 #2
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.

Jun 22 '06 #3
> In article <ma***************************************@python. org>,
"Girish Sahani" <gi****@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


Jun 22 '06 #4
In article <ma***************************************@python. org>,
Girish Sahani <gi****@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/...j/ur0606j.html >
and related materials.
and its referents.
Jun 22 '06 #5
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/Coo.../Recipe/496724

anton
Jun 22 '06 #6

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

Jun 22 '06 #7
Girish Sahani wrote:
In article <ma***************************************@python. org>,
"Girish Sahani" <gi****@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/
Jun 22 '06 #8
>> 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


Jun 23 '06 #9
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']

Jun 23 '06 #10
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))
Jun 23 '06 #11
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)
Jun 26 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Laphan | last post by:
Hi All This is a strange request, but I just cannot fathom how to do it. In theory the requirement is very basic, but in practise its a noodle!! I have 10 team names like so: Team A Team...
10
by: Steve Goldman | last post by:
Hi, I am trying to come up with a way to develop all n-length permutations of a given list of values. The short function below seems to work, but I can't help thinking there's a better way. ...
9
by: Jeff Kish | last post by:
Hi. I realize this might be more of a "figure out the algorithm" thing than strictly an std question.. sorry if it is off topic? It certainly was in the other group! Also, I'm pretty old, not...
13
by: Kiran Dalvi | last post by:
Hi, Can anybody please suggest me an efficient approach to find out all possible permutations of a String. e.g. My input string = "ABC". My program should give an output like .... ABC, ACB, BAC,...
4
by: darin dimitrov | last post by:
Hello, I need help with an algoritm that given a set of "n" distinct numbers will generate all the possible permutations of fixed length "m" of these numbers WITH repetitions (a total of n^m...
8
by: girish | last post by:
Hi, I want to generate all non-empty substrings of a string of length >=2. Also, each substring is to be paired with 'string - substring' part and vice versa. Thus, gives me , , , , , ] etc....
20
by: anurag | last post by:
hey can anyone help me in writing a code in c (function) that prints all permutations of a string.please help
0
by: JosAH | last post by:
Greetings, last week I stated that a lot of topics in a lot of forums mention all sorts of sorting problems. Last week's tip gave an answer to quite a bit of those sorting problems. Another...
2
by: Assimalyst | last post by:
Hi I have a Dictionary<string, List<string>>, which i have successfully filled. My problem is I need to create a filter expression using all possible permutations of its contents. i.e. the...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.