http://qs321.pair.com?node_id=197008


in reply to Re: (tye)Re: Finding all Combinations
in thread Finding all Combinations

sub combinations { my @list= @_; # List of items to choose from my @pick= (0) x @list; # Whether we want each item # $pick[$i] means include $list[$i] in results. # So @pick currently describes the empty subset. # Return a closure that, each time it is called, returns # the next subset: return sub { # Treat @pick as a base-2 number and increment it. # Note that @pick started as all 0s and we stop # after it is all 1s so all cases get covered. # (See original node for handling the empty subset) # Start at least-significant bit, $pick[0]: my $i= 0; # Increment a bit. If the bit was already 1, then # set it to 0 and continue to next bit: while( 1 < ++$pick[$i] ) { $pick[$i]= 0; # If we've run out of bits, then we were at # all 1s and so are done. Return empty list: return if $#pick < ++$i; } # The grep() below returns the indices for which # $pick[$_] is not 0. The @list[...] is an array # slice that returns the list of elements of @list # at the indices returned by grep. That is, we # return all items $list[$i] where $pick[$i] is # not 0. Same as: # map { $pick[$_] ? $list[$_] : () } 0..$#list; return @list[ grep $pick[$_], 0..$#pick ]; }; } my $next= combinations( 50..59 ); my @comb; while( @comb= $next->() ) { # do work with @comb here }

Does that help?

        - tye (but my friends call me "Tye")

Replies are listed 'Best First'.
Re: (tye)Re2: Finding all Combinations
by redbeard (Beadle) on Sep 11, 2002 at 22:36 UTC
    Indeed - I'm not as familiar with binary, so I'll have to ponder a bit, but thanks! I was working on this problem and was working on an algorithm that would iterate through all combos, but the checking back to see if you were REALLY done once you had reached the end of a set was killer for large sets (e.g. 30)...

      Change the while condition to:     while( 9 < ++$pick[$i]  ) { and the return statment to     return reverse @pick; and it will count in base 10. Perhaps that will make it easier to understand what it was doing.

              - tye (but my friends call me "Tye")