# Combinatorics Problem

Discussion in 'Perl Misc' started by Mitch McBride, Mar 1, 2007.

1. ### Mitch McBrideGuest

I have a problem who's solution requires functionality beyond what
Math::Combinatorics and other combinatorics modules offer. I need a
way of selecting combinations from different "buckets" that are
represented as nested arrays. For instance, the array @n = (['1','2'],
['a','b'],['y','z']) would return:

1 a y
2 a y
1 b y
2 b y
1 a z
2 a z
1 b z
2 b z

Math::Combinatorics prints the array reference when I try using nested
arrays. Anyone know of a module that can perform this type of
combination? Thanks!

#!/usr/bin/perl -w

use Math::Combinatorics;

my @n = (['1','2'],['a','b'],['y','z']);
print join("\n", map { join " ", @\$_ } combine(3,@n)),"\n";
print "\n";

OUTPUT:

Mitch McBride, Mar 1, 2007

2. ### Guest

On Feb 28, 6:10 pm, "Mitch McBride" <> wrote:
> I have a problem who's solution requires functionality beyond what
> Math::Combinatorics and other combinatorics modules offer. I need a
> way of selecting combinations from different "buckets" that are
> represented as nested arrays. For instance, the array @n = (['1','2'],
> ['a','b'],['y','z']) would return:
>
> 1 a y
> 2 a y
> 1 b y
> 2 b y
> 1 a z
> 2 a z
> 1 b z
> 2 b z
>

Try Iterator::Util;

use strict;
use warnings;
use Iterator::Util;

my @elements = ( [1, 2], [ qw/a b/ ], [ qw/y z/ ] );
my @iters = map iarray(\$_), @elements;
my @values = map \$_->value, @iters;

while ( @elements > grep { \$_ } map \$_->is_exhausted, @iters ) {

display(@values);

for (my \$i = 0; \$i < @iters; ++\$i) {
if (\$iters[\$i]->is_exhausted) {
\$iters[\$i] = iarray( \$elements[\$i] );
\$values[\$i] = \$iters[\$i]->value();
} else {
\$values[\$i] = \$iters[\$i]->value();
last;
}
}
}

display(@values);

sub display {
print join " => ", @_;
print "\n";
}

__END__

I and the author of Iterator::Util
both recommend the book 'Higher Order Perl'
by Mark Jason Dominus for its coverage
of iterators.

--
Hope this helps,
Steven

, Mar 1, 2007

3. ### Guest

On Feb 28, 10:46 pm, ""
<> wrote:
> On Feb 28, 6:10 pm, "Mitch McBride" <> wrote:
>

(snipped)

> Try Iterator::Util;
>

(snipped)

Of course, the while loop itself
can or should be replaced by an iterator:

use Iterator;
use Iterator::Util;

sub myiter {
my @elements = @_;
my @iters = map iarray(\$_), @elements;
my @values;

return Iterator->new( sub
{
Iterator::is_done if @elements == grep { \$_ } map \$_-
>is_exhausted,

@iters;
unless (@values) {
@values = map \$_->value, @iters;
} else {
for (my \$i = 0; \$i < @iters; ++\$i) {
if (\$iters[\$i]->is_exhausted) {
\$iters[\$i] = iarray( \$elements[\$i] );
\$values[\$i] = \$iters[\$i]->value();
} else {
\$values[\$i] = \$iters[\$i]->value();
last;
}
}
}
return [ @values ];
}
);
}

my @elements = ( [1, 2], [ qw/a b/ ], [ qw/y z/ ] );

my \$it = myiter(@elements);

do {
my \$foo = \$it->value();
display(@\$foo) if @\$foo;
} until \$it->is_exhausted;

sub display {
print join " => ", @_;
print "\n";
}

--
Cheers,
Steven

, Mar 1, 2007
4. ### Mitch McBrideGuest

On Mar 1, 2:30 am, "~greg" <> wrote:
> "Mitch McBride"> wrote
>
> > ... I need a way of selecting combinations from different "buckets"
> > that are represented as nested arrays.
> > For instance, the array @n = (['1','2'], ['a','b'],['y','z']) would return:
> > 1 a y
> > 2 a y
> > 1 b y
> > 2 b y
> > 1 a z
> > 2 a z
> > 1 b z
> > 2 b z

>
> use strict;
> use warnings;
> use Data:ump qw(dump);
>
> \$|=1;
>
> my @n = ( ['1','2'], ['a','b'],['y','z'] );
>
> sub Comb
> {
> if(@_ == 1)
> {
> return map { [\$_] } @{ \$_[0] };
> }
> my @A = Comb( @_[0..\$#_-1] );
> my @B = @{ \$_[\$#_] };
> my (\$a,\$b);
> return map{ \$a=\$_; map{ \$b=\$_; [@{\$a},\$b] } @B} @A;
>
> }
>
> # The basic idea is that to combine
> # ( ['1','2'], ['a','b'],['y','z'] )
> # you first combine
> # ( ['1','2'], ['a','b'] ),
> # getting
> # ( ['1','a'], ['1','b'], ['2','a'], ['2','b'] )
> # Then you append each element in ['y','z']
> # to each of those arrays, getting:
>
> my @m = Comb(@n);
> dump(\@m);
>
> #[
> # [1, "a", "y"],
> # [1, "a", "z"],
> # [1, "b", "y"],
> # [1, "b", "z"],
> # [2, "a", "y"],
> # [2, "a", "z"],
> # [2, "b", "y"],
> # [2, "b", "z"],
> #]
> # in lexicographical order.
>
> # note: the recursion has to start by turning ( ['1','2'] )
> # into ( ['1'], ['2'] )
>
> # ~greg

Thanks for the replies! I found just found Set::CrossProduct. It
solves this problem quite elegantly:

use Set::CrossProduct;

my @n = ( ['1','2'],['a','b'],['y','z'] );

my \$iterator = Set::CrossProduct->new( \@n );
my @tuples = \$iterator->combinations;
print map{"@\$_\n"} @tuples;

One caveat is that single elements like the one in ( '1' ,['a','b'],
['y','z'] ) must be expressed in an array like so ( ['1'],['a','b'],
['y','z'] ).

Mitch McBride, Mar 1, 2007