Unyeilding a permutation generator
Hello, can someone please help.
I found the following code at http://code.activestate.com/recipes/252178/
def all_perms(str):
if len(str) <=1:
yield str
else:
for perm in all_perms(str[1:]):
for i in range(len(perm)+1):
#nb str[0:1] works in both string and list contexts
yield perm[:i] + str[0:1] + perm[i:]
which allows me to do things like
for x in all_permx("ABCD"):
print x
I believe it is making use of the plain changes / Johnson Trotter
algorithm.
Can someone please confirm?
Anyway what I want to do is experiment with code similar to this (i.e.
same algorithm and keep the recursion) in other languages,
particularly vbscript and wondered what it would look like if it was
rewritten to NOT use the yield statement - or at least if it was
amended so that it can be easily translated to other languages that
dont have python's yield statement. I think the statement "for perm in
all_perms(str[1:]):" will be hardest to replicate in a recursive
vbscript program for example.
Thanks for any constructive help given.
Hal
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On Nov 3, 4:24 pm, Michele Simionato <[EMAIL PROTECTED]>
wrote:
> On Nov 2, 10:34 pm, [EMAIL PROTECTED] wrote:
>
> > Anyway what I want to do is experiment with code similar to this (i.e.
> > same algorithm and keep the recursion) in other languages,
> > particularly vbscript and wondered what it would look like if it was
> > rewritten to NOT use the yield statement - or at least if it was
> > amended so that it can be easily translated to other languages that
> > dont have python's yield statement. I think the statement "for perm in
> > all_perms(str[1:]):" will be hardest to replicate in a recursive
> > vbscript program for example.
>
> > Thanks for any constructive help given.
>
> Here is a solution which does not use yield, translittered
> from some Scheme code I have:
>
> def perm(lst):
> ll = len(lst)
> if ll == 0:
> return []
> elif ll == 1:
> return [lst]
> else:
> return [[el] + ls for el in lst
> for ls in perm([e for e in lst if not e==el])]
>
> if __name__ == '__main__':
> print perm('abcd')
Thats interesting code but seems to give a different output,
suggesting thet the underlying algorithm is different.
Ignoring linebreaks and case, the original code gives:
abcd bacd bcad bcda acbd cabd cbad cbda acdb cadb cdab cdba abdc badc
bdac bdca adbc dabc dbac dbca adcb dacb dcab dcba
The output from the above program, when converted to strings is:
abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb
cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba
Cheers, Hal.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On 2 Nov, 22:03, Carsten Haese <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > Anyway what I want to do is experiment with code similar to this (i.e.
> > same algorithm and keep the recursion) in other languages,
> > particularly vbscript and wondered what it would look like if it was
> > rewritten to NOT use the yield statement
>
> An obvious (though memory-inefficient) replacement is to accumulate a
> list and return the list. Initialize a result variable to an empty list,
> and instead of yielding elements, append them to the result variable.
> Then return the result variable at the end of the function.
>
> HTH,
>
> --
> Carsten Haesehttp://informixdb.sourceforge.net
That did it and I can still understand it!
def allperm(str):
if len(str) <= 1:
return str
else:
biglist = []
for perm in allperm(str[1:]):
for i in xrange(len(str)): #minor change here
biglist.append(perm[:i] + str[0:1] + perm[i:])
return biglist
for x in allperm("ABCD"):
print x
--
http://mail.python.org/mailman/listinfo/python-list
