http://qs1969.pair.com?node_id=371228
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";
}
Replies are listed 'Best First'.
Re: Iterating over combinations
by Limbic~Region (Chancellor) on Sep 22, 2004 at 22:13 UTC
    blokhead,
    When I was working on this, I noticed revdiablo was generating all combinations of all sizes. I came up with a working solution to find only combinations of the desired size though it wasn't very elegant. I then sat down to figure out how I could make it generic for any size combinations (without having found this node) and came up with the following: 
    #!/usr/bin/perl
use strict;
use warnings;

my $iter = combo( 5 , 1 .. 50  );
while ( my @combo = $iter->() ) {
    print "@combo\n";
}

sub combo {
    my $by = shift;
    return sub { () } if ! $by || $by =~ /\D/ || @_ < $by;
    my @list = @_;

    my @position = (0 .. $by - 2, $by - 2);
    my @stop     = @list - $by .. $#list;
    my $end_pos  = $#position;
    my $done     = undef;

    return sub {
        return () if $done;
        my $cur = $end_pos;
        {
            if ( ++$position[ $cur ] > $stop[ $cur ] ) {
                $position[ --$cur ]++;
                redo if $position[ $cur ] > $stop[ $cur ];
                my $new_pos = $position[ $cur ];
                @position[ $cur .. $end_pos ] = $new_pos .. $new_pos +
+ $by;
            }
        }
        $done = 1 if $position[0] == $stop[0];
        return @list[ @position ];
    }
}

    [download]
    I didn't spend a lot of time benchmarking it. In some cases it does better than yours and then in others it does much worse. In any case, since I went through the trouble I figured I would add it here (now that I found it) in the spirit of TIMTOWTDI.

    Cheers - L~R

    Update: I kept the algorithm the same, but I made numerous optimizations. It is now much faster in the best case and only marginally slower than your method in the worst cases. The original is in HTML comments if anyone is interested.

[reply]
[d/l]
Re: Iterating over combinations
by Anonymous Monk on Feb 24, 2011 at 17:25 UTC
    Another solution... 
    ### Example Usage:
my $Text = "The quick brown fox jumps over the lazy dog";
my @Words = split(/ /, $Text);
printf("%s (%d words)\n", $Text, scalar @Words);
print "-"x100 . "\n";

foreach my $I (1..3) {
  my @Results = Combinations($I, @Words);
  printf("Found %d combinations of %d words from '%s'\n", 
     scalar @Results, $I, $Text);
  printf("   (%s)\n", join("|", @$_) ) foreach (@Results);
  print "-"x100 . "\n";
}

### Actual Useful Part:
sub Combinations {
  my $PickSize = shift;
  my @Elements = @_;
  my @RValue;

  my $StopAt    = scalar(@Elements) - ($PickSize-1) - 1;
  return ([]) if $PickSize == 0;
  return ([]) if $PickSize > scalar(@Elements);
  for(my $i=0; $i<=$StopAt; $i++) {
    my $Element = $Elements[$i];
    my @Rest = @Elements;
    splice(@Rest, 0, $i+1);

    foreach ( Combinations($PickSize-1, @Rest) ) {
      my @NewElement = ($Element, @$_);
      push(@RValue, \@NewElement );
    }
  }
  return @RValue;                                       
}

    [download]
[reply]
[d/l]