473,321 Members | 1,778 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,321 software developers and data experts.

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
Nov 2 '08 #1
13 2217
si******@yahoo.com writes:
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 -
Without the yield statement and keeping the same space complexity, you
basically have to wrap the enumeration state in a data object that you
can enumerate over explicitly. That in turn may mean you have to
unwind the recursion into old fashioned stack operations.
Nov 2 '08 #2
si******@yahoo.com 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 Haese
http://informixdb.sourceforge.net
Nov 2 '08 #3
On Nov 2, 3:34*pm, silly...@yahoo.com wrote:
Hello, can someone please help.

I found the following code athttp://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
I think multi-threading is the "truest" to the original. You might
develop a framework to set events when particular generators are to
take a turn, place their "yields", per se, in a particular place, set
the return event, etc., and reuse it. Of course, starting threads in
VBS might be another matter.
Nov 2 '08 #4
si******@yahoo.com wrote:
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.
There are various approaches you could use, the simplest of which is to
provide a "callback function" as an additional argument to the all_perms
function, and call it with the permutation as an argument in place of
the yield statement.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/

Nov 3 '08 #5
Steve Holden wrote:
si******@yahoo.com 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.
There are various approaches you could use, the simplest of which is to
provide a "callback function" as an additional argument to the all_perms
function, and call it with the permutation as an argument in place of
the yield statement.
I had thought of three ways to avoid yield, that makes a fourth.

Summary:

1. Think of generator function as an abbreviated iterator class and
unabbreviate by writing a full iterator class with .__next__ (3.0).
+ Transparent to caller
- Will often have to re-arrange code a bit to save locals values as
attributes before returning. If there is an inner loop, efficiency may
require copying attributes to locals.

2. Add to collection rather than yield, then return collection rather
than raise StopIteration.
+ Transparent to caller; small change to function.
- Returned collection can be arbitrarily large and take an arbitrarily
long time to collect.

3. Add callback parameter and change 'yield value' to 'callback(value)'.
+ Minor change to generator function.
- Minor to major change to caller to turn consumer code into a callback
that somehow gets result of callback to where it is needed. (Avoiding
the major changes sometimes needed was one of the motivations for
generators.)

4. Combine caller and generator code by inlining one into or around the
other.
+ Neither code will change much.
- Loss benefit of modularity and reuse without cut-and-paste, which is
subject to error.

I have not thought through yet how well each of these work with
recursive generators.

Conclusion:

Generators with yield make Python a great language for expressing
combinatorial algorithms.

Terry Jan Reedy

Nov 3 '08 #6
On Nov 2, 10:34*pm, silly...@yahoo.com 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')
Nov 3 '08 #7
On Sun, 2 Nov 2008 14:09:01 -0800 (PST), Aaron Brady <ca********@gmail.comwrote:
On Nov 2, 3:34*pm, silly...@yahoo.com wrote:
....
>for x in *all_permx("ABCD"):
* print x
....
I think multi-threading is the "truest" to the original. You might
develop a framework to set events when particular generators are to
take a turn, place their "yields", per se, in a particular place, set
the return event, etc., and reuse it. Of course, starting threads in
VBS might be another matter.
Why multi-threading? I see no concurrency in the original algorithm.
There is, in my mind, nothing concurrent about 'yield'.

/Jorgen

--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.se R'lyeh wgah'nagl fhtagn!
Nov 3 '08 #8
On Mon, 03 Nov 2008 21:09:58 +0000, Jorgen Grahn wrote:
Why multi-threading? I see no concurrency in the original algorithm.
There is, in my mind, nothing concurrent about 'yield'.
No "real" concurrency but a generator can be seen as independent thread
of code where the generator code is allowed to run when `next()` is
called and stops itself when it ``yield``\s an object. Sort of
cooperative multitasking. The name "yield" is often used in concurrent
code like Java's or Io's `yield()` methods.

Ciao,
Marc 'BlackJack' Rintsch
Nov 3 '08 #9
On Nov 3, 4:13*pm, Marc 'BlackJack' Rintsch <bj_...@gmx.netwrote:
On Mon, 03 Nov 2008 21:09:58 +0000, Jorgen Grahn wrote:
Why multi-threading? *I see no concurrency in the original algorithm.
There is, in my mind, nothing concurrent about 'yield'.

No "real" concurrency but a generator can be seen as independent thread
of code where the generator code is allowed to run when `next()` is
called and stops itself when it ``yield``\s an object. *Sort of
cooperative multitasking. *The name "yield" is often used in concurrent
code like Java's or Io's `yield()` methods.

Ciao,
* * * * Marc 'BlackJack' Rintsch
Further, it resumes where it left off when it gets control again:

"execution is stopped at the yield keyword (returning the result) and
is resumed there when the next element is requested by calling the
next() method" --the fine manual

It maintains and operates in its own separate execution frame, etc.
Nov 3 '08 #10
On Nov 3, 4:24*pm, Michele Simionato <michele.simion...@gmail.com>
wrote:
On Nov 2, 10:34*pm, silly...@yahoo.com 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.
Nov 3 '08 #11
On 2 Nov, 22:03, Carsten Haese <carsten.ha...@gmail.comwrote:
silly...@yahoo.com 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
Nov 4 '08 #12
si******@yahoo.com writes:
[...]
Thats interesting code but seems to give a different output,
suggesting thet the underlying algorithm is different.
Yes.

Yours takes the first element out of the list and inserts it in every
position of all the permutations of the list without the first element:
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
Michele's takes every element out of the list in turn and appends every
permutation of the list without this element to its right:
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.
--
Arnaud
Nov 4 '08 #13
On Nov 3, 11:45*pm, silly...@yahoo.com wrote:
>
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
Note:

items = [''.join(p) for p in perm('abcd') ]
assert items == sorted(items)
items = list(all_perms('abcd'))
assert items != sorted(items)
Nov 4 '08 #14

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

Similar topics

10
by: Talin | last post by:
I'm sure I am not the first person to do this, but I wanted to share this: a generator which returns all permutations of a list: def permute( lst ): if len( lst ) == 1: yield lst else: head =...
3
by: Jack Middleton | last post by:
Hi! I'm lookin for a faster permutation algorithm for matrices. I know that it can be done with multiplying a matrix with a permutation matrix. It just seems a waste to iterate through all those...
1
by: user | last post by:
Hello I have Array of 50 ints. I want to receive random permutation, so in each int will be different number from 0-49. Is there any class for permutation ? Thanx Michal
6
by: Rajesh | last post by:
Hello Everybody, Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3),...
2
by: robert | last post by:
for the purpose of flat n-dim iteration a function or generator ndim_permute(*v) should compute or generate a list of tuples like: ndim_permute( (0,1,2), (0,1), (0,1), ) -> 0 0 0 0 0 1 0 0 2...
3
by: weidongtom | last post by:
Hi, I have been working at this problem, and I think I need a permutation algorithm that does the following: Given a list of elements that are either a character or a character follows by a...
6
by: badcrusher10 | last post by:
Hello. I'm having trouble figuring out what to do and how to do.. could someone explain to me what I need to do in order to work? THIS IS WHAT I NEED TO DO: Professor Snoop wants a program...
7
by: xirowei | last post by:
Let's say i create a String array that store 4 Alphabets {"A","B","C","D"} How can i get the result if i need permutation of 4P3 and 4P2? I had refer to many examples from the internet, but...
0
by: 249740 | last post by:
Write a program that reads N phrases and determines if one phrase is a permutation of the other. For example: Phrase 1 is: “One World One Dream” Phrase 2 is: “World One One Dream”. Then the output...
0
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
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
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.