Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

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!


Replies are listed 'Best First'.
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!


    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?

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (1)
As of 2023-06-06 02:40 GMT
Find Nodes?
    Voting Booth?
    How often do you go to conferences?

    Results (26 votes). Check out past polls.