|Pathologically Eclectic Rubbish Lister|
Re^8: Perl6 Contest: Test your Skillsby blokhead (Monsignor)
|on May 23, 2005 at 20:29 UTC ( #459702=note: print w/replies, xml )||Need Help??|
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:
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 exceeds 4, when $pick 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:
This initializes @pick to our starting point and returns the array slice all in one shot.
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.
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!
In Section Seekers of Perl Wisdom