### Re: (tye)Re: Finding all Combinations

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

in reply to (tye)Re: 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!

Replies are listed 'Best First'.
(tye)Re2: Finding all Combinations
by tye (Sage) 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")

Create A New User
Node Status?
node history
Node Type: note [id://196832]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2018-04-22 19:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (83 votes). Check out past polls.

Notices?