Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Combinatorics Problem

Reply
Thread Tools

Combinatorics Problem

 
 
Mitch McBride
Guest
Posts: n/a
 
      03-01-2007
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(0x9ad0c2 ARRAY(0x9ae7b0c) ARRAY(0x9b94b50)

 
Reply With Quote
 
 
 
 
attn.steven.kuo@gmail.com
Guest
Posts: n/a
 
      03-01-2007
On Feb 28, 6:10 pm, "Mitch McBride" <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
 
attn.steven.kuo@gmail.com
Guest
Posts: n/a
 
      03-01-2007
On Feb 28, 10:46 pm, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> On Feb 28, 6:10 pm, "Mitch McBride" <(E-Mail Removed)> 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

 
Reply With Quote
 
Mitch McBride
Guest
Posts: n/a
 
      03-01-2007
On Mar 1, 2:30 am, "~greg" <(E-Mail Removed)> 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'] ).

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Combinatorics Michael Robertson Python 12 02-13-2008 07:21 PM
Python and Combinatorics none Python 4 10-26-2007 07:41 AM
Python and Combinatorics Nic Python 4 05-16-2006 09:41 AM
[perl-python] combinatorics fun Xah Lee Python 7 02-11-2005 10:05 AM
combinatorics question Carnosaur C Programming 17 10-31-2003 03:48 PM



Advertisments