Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Recursively-generated Iterators

by kelan (Deacon)
on May 19, 2005 at 21:01 UTC ( #458789=note: print w/replies, xml ) Need Help??

in reply to Recursively-generated Iterators

Here's another iterator solution that avoids the recursion altogether. There are three differences:

  • It will return undef instead of an empty array ref if the number of items is less than the amount to choose (ie 3 choose 5).
  • The amount to choose is passed before the list of items instead of afterwards because I thought it was weird, although your way does make sense if one thinks of it like "Here are 50 things, choose 5".
  • The output order is a bit different.
All three of these can certainly be fixed, but I wanted to keep the code clear.
sub choose_n_iter { my @todo = [ shift, [ @_ ], [] ]; return sub { while ( @todo ) { my ( $n, $pool, $tally ) = @{ shift @todo }; return $tally if $n == 0; next if @$pool == 0; my ( $first, @rest ) = @$pool; push @todo, [ $n - 1, \@rest, [ @$tally, $first ]], [ $n , \@rest, $tally ]; } return; }; }
And here is a more effecient version:
sub choose_n_iter { my @todo = [ shift, [ @_ ], [] ]; return sub { while ( @todo ) { my ( $n, $pool, $tally ) = @{ shift @todo }; return $tally if $n == 0; return [ @$tally, @$pool ] if $n == @$pool; next if @$pool == 0; my ( $first, @rest ) = @$pool; push @todo, [ $n - 1, \@rest, [ @$tally, $first ]]; push @todo, [ $n , \@rest, $tally ] if @res +t; } return; }; }
Thanks goes out to HOP for the recursion-to-iterator help.

Replies are listed 'Best First'.
Re^2: Recursively-generated Iterators
by Roy Johnson (Monsignor) on May 23, 2005 at 15:57 UTC
    Your solution is more traditional. It does essentially the same thing as mine — delaying evaluation of later elements until they're needed — by keeping an explicit stack (or what should be a stack, but you seem to be using it as a queue, which explains the different order of return values). You note that it "avoids recursion altogether", but that's not really a legitimate goal. Recursion is not a bad thing in and of itself. It is often a very helpful thing.

    The reason I think my solution is an improvement is that it saves you the trouble of manipulating a stack, and allows the iterative solution to more closely resemble the recursive one. In a word: simplicity. You can follow a foolproof recipe, and in five or ten minutes have an iterator that returns exactly the same set as the recursive one. Same order, same structure, same arguments. Here's the recipe (this is new since my original post):

    1. Empty-set return values are replaced by empty subs
    2. Explicit (non-recursing) return values are assigned to an array; the iterator will be a sub that shifts that array
    3. A list of return values that includes recursive calls is replaced by a list of sub-wrapped iterators (wrapping the iterator calls in subs delays their evaluation), the iterator will be a sub that shifts its way through that list, unwrapping iterators until it finds one that returns something.
    4. See the rewrite of iter_choose_n (at the end of this post) for what to do when you have to accumulate data with a recursive call, as choose_n does (but Hanoi doesn't).
    That last is a little complicated to describe in words, so I'll demonstrate with Towers of Hanoi.

    Rewriting iter_choose_n to work with the boilerplate:

    Caution: Contents may have been coded under pressure.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://458789]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2017-01-21 05:42 GMT
Find Nodes?
    Voting Booth?
    Do you watch meteor showers?

    Results (182 votes). Check out past polls.