Combinatorics Problem

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

  1. 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)
     
    Mitch McBride, Mar 1, 2007
    #1
    1. Advertising

  2. Mitch  McBride

    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
    #2
    1. Advertising

  3. Mitch  McBride

    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
    #3
  4. 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::Dump 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
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Carnosaur

    combinatorics question

    Carnosaur, Oct 28, 2003, in forum: C Programming
    Replies:
    17
    Views:
    567
    Carnosaur
    Oct 31, 2003
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    401
    bruno modulix
    Feb 11, 2005
  3. Nic

    Python and Combinatorics

    Nic, May 16, 2006, in forum: Python
    Replies:
    4
    Views:
    1,744
    Gerard Flanagan
    May 16, 2006
  4. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    528
    Gerard Flanagan
    Oct 26, 2007
  5. Michael Robertson

    Combinatorics

    Michael Robertson, Feb 12, 2008, in forum: Python
    Replies:
    12
    Views:
    932
    Paul Hankin
    Feb 13, 2008
Loading...

Share This Page