snippet
blokhead
<b>Semantic nitpicking:</b>
<ul>
<li> A <i>permutation</i> of a set is a rearrangement of its items, using all the items, where order is important.
<li> The <i>power set</i> of a set is all of its possible subsets (order is not important within subsets).
<li> A <i>combination</i> "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, <i>combinations are when we specify the size of the subsets taken.</i>
</ul>
[id://128293] 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). [id://29374] is a canonical way to iterate over permutations.
<p>
Here are some ways to iterate over <code>@S</code> choose <code>$K</code>, all the <code>$K</code>-sized subsets of <code>@S</code>.
<code>
## Filtering tye's "combinations" (power set) iterator:
my $iter = combinations(@S);
while ( my @c = $iter->() ) {
next unless @c == $K;
...
}
</code>
<code>
## Using tye's Algorithm::Loops:
NestedLoops(
[ 0 .. $#S ],
( sub { [$_+1 .. $#S] } ) x ($K - 1),
sub { my @c = @S[@_]; ... }
}
</code>
Finally, the code below which uses a similar principle as [id://128293], keeping track of a list of indices. The subsets are returned in the same order as a nested for-loop.
<p>
<b>Update:</b> see [id://459702] for a verbose explanation of what this code does.
<CODE>
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];
};
}
</code>
You use it like this:
<code>
my $iter = combinations( 3 => ['a' .. 'f'] );
while ( my @c = $iter->() ) {
print "@c\n";
}
</CODE>