Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: (tye)Re: Finding all Combinations

by redbeard (Beadle)
on Sep 10, 2002 at 23:48 UTC ( #196832=note: print w/ replies, xml ) Need Help??


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

That's fantastic - I was wondering if you could perhaps help out an initiate such as myself and comment that code - what it's doing and why, as I'm having a bit of a hard time following it and would like to learn the methodology behind it (as i believe i was trying to domsething similar but failed completely). Thanks!


Comment on Re: (tye)Re: Finding all Combinations
(tye)Re2: Finding all Combinations
by tye (Cardinal) on Sep 11, 2002 at 17:38 UTC
    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")
      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")

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://196832]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (6)
As of 2014-07-10 07:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (202 votes), past polls