Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re^8: Perl6 Contest: Test your Skills

by blokhead (Monsignor)
on May 23, 2005 at 20:29 UTC ( #459702=note: print w/ replies, xml ) Need Help??


in reply to Re^7: Perl6 Contest: Test your Skills
in thread Perl6 Contest: Test your Skills

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
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;
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 );
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;
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!

blokhead


Comment on Re^8: Perl6 Contest: Test your Skills
Select or Download Code
Re^9: Perl6 Contest: Test your Skills
by thor (Priest) on May 25, 2005 at 18:52 UTC
    This'll give me something to stew on for a while. Thanks for the detailed write-up!

    thor

    Feel the white light, the light within
    Be your own disciple, fan the sparks of will
    For all of us waiting, your kingdom will come

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://459702]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (9)
As of 2014-09-22 09:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (185 votes), past polls