|Perl: the Markov chain saw|
Re^8: Perl6 Contest: Test your Skillsby blokhead (Monsignor)
|on May 23, 2005 at 20:29 UTC||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!