Iterating over combinations

Description:

Semantic nitpicking:

A permutation of a set is a rearrangement of its items, using all the items, where order is important.
The power set of a set is all of its possible subsets (order is not important within subsets).
A combination "N choose K" is the number of ways to choose K things from N things (where the order of the K things doesn't matter). Often, math textbooks extend this notation to "S choose K", where S is a set instead of a number, to mean the set of all K-sized-subsets of S. In short, combinations are when we specify the size of the subsets taken.

(tye)Re: Finding all Combinations is a canonical way to iterate over a set's power set. It won't get you combinations in the above sense (a better name would be (tye)Re: Finding all Subsets). Permuting with duplicates and no memory is a canonical way to iterate over permutations.

Here are some ways to iterate over @S choose $K, all the $K-sized subsets of @S.

## Filtering tye's "combinations" (power set) iterator:
my $iter = combinations(@S);
while ( my @c = $iter->() ) {
    next unless @c == $K;
    ...
}
[download]

## Using tye's Algorithm::Loops:
NestedLoops(
    [ 0 .. $#S ],
    ( sub { [$_+1 .. $#S] } ) x ($K - 1),
    sub { my @c = @S[@_]; ... }
}
[download]

Finally, the code below which uses a similar principle as (tye)Re: Finding all Combinations, keeping track of a list of indices. The subsets are returned in the same order as a nested for-loop.

Update: see Re^8: Perl6 Contest: Test your Skills for a verbose explanation of what this code does.

sub combinations {
    my ($num, $arr) = @_;

    return sub { return }
        if $num == 0 or $num > @$arr;

    my @pick;

    return sub {
        return @$arr[ @pick = ( 0 .. $num - 1 ) ]
            unless @pick;
        
        my $i = $#pick;
        $i-- until $i < 0 or $pick[$i]++ < @$arr - $num + $i;
        return if $i < 0;

        @pick[$i .. $#pick] = $pick[$i] .. $#$arr;
        
        return @$arr[@pick];
    };
}

You use it like this:

my $iter = combinations( 3 => ['a' .. 'f'] );

while ( my @c = $iter->() ) {
    print "@c\n";
}