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.
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; next if @$pool == 0; my ( $first, @rest ) = @$pool; push @todo, [ $n - 1, \@rest, [ @$tally, $first ]], [ $n , \@rest, $tally ]; } return; }; }
Thanks goes out to HOP for the recursion-to-iterator help.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; }; }
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Recursively-generated Iterators
by Roy Johnson (Monsignor) on May 23, 2005 at 15:57 UTC |
In Section
Meditations