On May 23, 2006, at 8:59 AM, Xavier Noria wrote:
use strict;
use warnings;
use Algorithm::Combinatorics qw(partitions);
my @data = qw(a b c d e);
my $iter = partitions([EMAIL PROTECTED], 2);
while (my $p = $iter->next) {
next unless @{$p->[0]} == 2 || @{$p->[0]} == 3;
print "(@$_)" for @$p;
print "\n";
}
% perl foo.pl
(a b c)(d e)
(a b d)(c e)
(a b e)(c d)
(a b)(c d e)
(a c d)(b e)
(a c e)(b d)
(a c)(b d e)
(a d e)(b c)
(a d)(b c e)
(a e)(b c d)
That algorithm works, but it's overkill for this example, though. It
generates all possible partitions into 2 sets, which is O(2^{n-1})
partitions (see http://en.wikipedia.org/wiki/
Stirling_number_of_the_second_kind), but if we want just the ones
with partition sizes k & n-k, that can be done in O(n-choose-k) which
can be quite a bit less (depending on n and k).
BTW, Xavier & David both: The proposed interface for enumerating the
set partitions uses array refs, but sets in perl are more naturally
represented using hashes. I'd suggest re-implementing in terms of
hashes, or perhaps giving it a complete-enough OO interface that
hides the actual implementation structure.
-Ken
