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 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
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.
> 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
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.
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/
>> 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
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']
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))
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) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...
|
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. ...
|
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...
|
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,...
|
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...
|
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....
|
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
|
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...
|
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...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
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...
|
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...
|
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...
|
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...
|
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...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
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
|
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...
| |