Re: Unyeilding a permutation generator
On 3 Nov 2008 22:13:42 GMT, Marc 'BlackJack' Rintsch <[EMAIL PROTECTED]> wrote: > On Mon, 03 Nov 2008 21:09:58 +, 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. Sort of ... I find it more useful to see it as an object, or something with a state. And I think it's a bad idea to rewrite an algorithm using threads in order to simulate generators. > The name "yield" is often used in concurrent > code like Java's or Io's `yield()` methods. That's a completely unrelated yield, isn't it? Meanings (1) and (3) respectively in http://en.wiktionary.org/wiki/yield: - To give way; to allow another to pass first. - To produce as return, as from an investment. /Jorgen -- // Jorgen Grahn R'lyeh wgah'nagl fhtagn! -- http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On Nov 3, 11:45 pm, [EMAIL PROTECTED] 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)
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
[EMAIL PROTECTED] 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 -- 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
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 Nov 3, 4:13 pm, Marc 'BlackJack' Rintsch <[EMAIL PROTECTED]> wrote: > On Mon, 03 Nov 2008 21:09:58 +, 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On Mon, 03 Nov 2008 21:09:58 +, 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On Sun, 2 Nov 2008 14:09:01 -0800 (PST), Aaron Brady <[EMAIL PROTECTED]> wrote:
> On Nov 2, 3:34 pm, [EMAIL PROTECTED] 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 R'lyeh wgah'nagl fhtagn!
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
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')
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
Steve Holden 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 - 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
[EMAIL PROTECTED] 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/
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
On Nov 2, 3:34 pm, [EMAIL PROTECTED] 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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
[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 Haese http://informixdb.sourceforge.net -- http://mail.python.org/mailman/listinfo/python-list
Re: Unyeilding a permutation generator
[EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
