Combinatorics Problem

[Mitch McBride]

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:
ARRAY(0x9ad0c28) ARRAY(0x9ae7b0c) ARRAY(0x9b94b50)

 

[attn.steven.kuo]

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.

 

[attn.steven.kuo]

(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";
}

 

[Mitch McBride]

"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'] ).