note
blokhead
Sorry about the code in [id://371228]. It is very very terse ;) Allow me to explain how it works:
<p>
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 <code>@$arr[@pick]</code>. 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:
<code>
@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
</code>
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.
<p>
This is almost the same, except now each digit has its own, <i>different</i> carry-over threshold. In this example, we carry when <code>$pick[2]</code> exceeds 4, when <code>$pick[1]</code> exceeds 3, etc. In general, <code>$pick[$i]</code> 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 <code>$pick[$i]</code>.
<p>
Now the code:
<code>
return @$arr[ @pick = ( 0 .. $num - 1 ) ]
unless @pick;
</code>
This initializes @pick to our starting point and returns the array slice all in one shot.
<code>
my $i = $#pick;
$i-- or return
while ( $pick[$i]++ == @$arr - $num + $i );
</code>
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.
<code>
@pick[$i .. $#pick] = $pick[$i] .. $#$arr;
</code>
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 <code>$pick[$i+1]</code>, 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.
<p>
Hope this helps!
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-137386">
<p>
blokhead
</div></div>
458728
459153