Sorry about the code in Iterating over combinations. It is very very terse ;) Allow me to explain how it works:

In iterating over $num-sized subsets of @arr: we maintain @pick, which are the $num indices of the array elements we will return. You see that we always return the array slice @$arr[@pick]. For example, suppose we have an array @arr of 5 items and want to iterate subsets of size 3. Then @pick takes on the values in this order:

@pick      @arr[@pick]

0 1 2  ==>  x x x . .
0 1 3  ==>  x x . x .
0 1 4  ==>  x x . . x
0 2 3  ==>  x . x x .
0 2 4  ==>  x . x . x
0 3 4  ==>  x . . x x
1 2 3  ==>  . x x x .
1 2 4  ==>  . x x . x
1 3 4  ==>  . x . x x
2 3 4  ==>  . . x x x
[download]

The iterator code simply "increments" @pick in this manner. It's a lot like incrementing a number in base 10: You start on the right and increment that digit. If it becomes a 10, you have to "carry over" to the left. At the first place a carry-over is not needed, you need to reset all the digits to the right to zeroes.

This is almost the same, except now each digit has its own, different carry-over threshold. In this example, we carry when $pick[2] exceeds 4, when $pick[1] exceeds 3, etc. In general, $pick[$i] must not exceed ($#arr + $i - $num). We start on the right and "carry over" to the left if a digit gets too big. Then when we "reset" the digits to the right, instead of resetting each one to 0, we must reset them to an increasing sequence starting at $pick[$i].

Now the code:

return @$arr[ @pick = ( 0 .. $num - 1 ) ]
    unless @pick;
[download]

This initializes @pick to our starting point and returns the array slice all in one shot.

my $i = $#pick;
$i-- or return
    while ( $pick[$i]++ == @$arr - $num + $i );
[download]

This is the super-terse part. Starting from the end of the array, increment a digit and then move backwards while a carry-over is necessary. If we have to carry over every digit ($i becomes 0), then we have to stop (return), there is nothing left we can do.

@pick[$i .. $#pick] = $pick[$i] .. $#$arr;
[download]

Now since $i is the last place we needed a carry, we have to reset the digits to the right of $i. There are some important edge cases: for instance, we don't want to talk about $pick[$i+1], since it's possible that $i is still $#pick (and we want @pick to stay the same size). Also, notice that, in general, the list on the RHS may be larger than necessary, just for simplicity.

Hope this helps!

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.