Permutations/combinations from multiple arrays

Discussion in 'Perl Misc' started by Peter Ensch, Jun 13, 2006.

  1. Peter Ensch

    Peter Ensch Guest

    Not sure if the correct word is permutation or combination (or neither), but
    this is what I want to do. Given an array of arrays, such as:

    my @v = (
    [qw/ a /],
    [qw/ b c d /],
    [qw/ e f g /],
    );

    I want to output all the permutations/combinations from taking one item
    from each array, like this:

    a b e
    a b f
    a b g
    a c e
    a c f
    a c g
    a d e
    a d f
    a d g

    The function should be able to handle any number of arrays with any
    number of elements in each array.

    This sounds easy but I'm stuck. Help!
    Peter

    --

    ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^
    Peter Ensch,
    A-1140 (214) 480 2333
    ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^
    Peter Ensch, Jun 13, 2006
    #1
    1. Advertising

  2. Peter Ensch

    Guest

    Peter Ensch <> wrote:
    > Not sure if the correct word is permutation or combination (or neither),
    > but this is what I want to do. Given an array of arrays, such as:
    >
    > my @v = (
    > [qw/ a /],
    > [qw/ b c d /],
    > [qw/ e f g /],
    > );
    >
    > I want to output all the permutations/combinations from taking one item
    > from each array, like this:
    >

    ....
    > The function should be able to handle any number of arrays with any
    > number of elements in each array.
    >
    > This sounds easy but I'm stuck. Help!


    google this group for "__Comb.pm__". It was about 2 years ago.

    Xho

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , Jun 13, 2006
    #2
    1. Advertising

  3. Peter Ensch wrote:
    > Not sure if the correct word is permutation or combination (or neither), but
    > this is what I want to do. Given an array of arrays, such as:
    >
    > my @v = (
    > [qw/ a /],
    > [qw/ b c d /],
    > [qw/ e f g /],
    > );
    >
    > I want to output all the permutations/combinations from taking one item
    > from each array, like this:
    >
    > a b e
    > a b f
    > a b g
    > a c e
    > a c f
    > a c g
    > a d e
    > a d f
    > a d g
    >
    > The function should be able to handle any number of arrays with any
    > number of elements in each array.
    >
    > This sounds easy but I'm stuck.


    It is easy. Could you be more precise about where you are stuck?

    Basically you need a recursive fuction that literates over one list and
    then calls itselft with fewer lists.

    For example...

    sub perm {
    my ($first_list,@remaining_lists) = @{shift()};
    # Remainder of @_ is the prefix
    return [ [ @_ ] ] unless $first_list;
    [ map { @{ perm( \@remaining_lists, @_, $_) } } @$first_list ];
    }
    Brian McCauley, Jun 13, 2006
    #3
  4. Peter Ensch

    Guest

    Peter Ensch wrote:
    > Not sure if the correct word is permutation or combination (or neither), but
    > this is what I want to do. Given an array of arrays, such as:
    >
    > my @v = (
    > [qw/ a /],
    > [qw/ b c d /],
    > [qw/ e f g /],
    > );
    >
    > I want to output all the permutations/combinations from taking one item
    > from each array, like this:
    >
    > a b e
    > a b f
    > a b g
    > a c e
    > a c f
    > a c g
    > a d e
    > a d f
    > a d g
    >
    > The function should be able to handle any number of arrays with any
    > number of elements in each array.
    >
    > This sounds easy but I'm stuck. Help!
    > Peter
    >
    > --
    >
    > ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^
    > Peter Ensch,
    > A-1140 (214) 480 2333
    > ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^


    You could do it with the Cross Product.

    #!/usr/bin/perl
    use strict;
    use warnings;
    use Set::CrossProduct;

    my @v = (
    [qw/ a /],
    [qw/ b c d /],
    [qw/ e f g /],
    );

    my $iterator = Set::CrossProduct->new( \@v );

    my @tuples = $iterator->combinations;

    print map{"@$_\n"} @tuples;

    **prints

    a b e
    a b f
    a b g
    a c e
    a c f
    a c g
    a d e
    a d f
    a d g
    , Jun 13, 2006
    #4
  5. Peter Ensch wrote:
    > Not sure if the correct word is permutation or combination (or neither), but
    > this is what I want to do. Given an array of arrays, such as:
    >
    > my @v = (
    > [qw/ a /],
    > [qw/ b c d /],
    > [qw/ e f g /],
    > );
    >
    > I want to output all the permutations/combinations from taking one item
    > from each array, like this:
    >
    > a b e
    > a b f
    > a b g
    > a c e
    > a c f
    > a c g
    > a d e
    > a d f
    > a d g
    >
    > The function should be able to handle any number of arrays with any
    > number of elements in each array.


    $ perl -le'
    my @v = (
    [qw/ a /],
    [qw/ b c d /],
    [qw/ e f g /],
    );
    print "@{[ /./g ]}" for glob join "", map { local $" = ","; "{@$_}" } @v;
    '
    a b e
    a b f
    a b g
    a c e
    a c f
    a c g
    a d e
    a d f
    a d g



    John
    --
    use Perl;
    program
    fulfillment
    John W. Krahn, Jun 13, 2006
    #5
  6. Peter Ensch

    Guest

    "John W. Krahn" <> wrote:
    > Peter Ensch wrote:
    > > Not sure if the correct word is permutation or combination (or
    > > neither), but this is what I want to do. Given an array of arrays, such
    > > as:
    > >
    > > my @v = (
    > > [qw/ a /],
    > > [qw/ b c d /],
    > > [qw/ e f g /],
    > > );
    > >
    > > I want to output all the permutations/combinations from taking one item
    > > from each array, like this:
    > >
    > > a b e
    > > a b f
    > > a b g
    > > a c e
    > > a c f
    > > a c g
    > > a d e
    > > a d f
    > > a d g
    > >
    > > The function should be able to handle any number of arrays with any
    > > number of elements in each array.

    >
    > $ perl -le'
    > my @v = (
    > [qw/ a /],
    > [qw/ b c d /],
    > [qw/ e f g /],
    > );
    > print "@{[ /./g ]}" for glob join "", map { local $" = ","; "{@$_}" } @v;
    > '


    I wouldn't recommend this as a general method for handling "any number of
    arrays with any number elements" for two reasons. One is that it builds
    the entire list in memory upfront, so it consumes massive amounts
    of memory for large results. The other is that it beats up your file
    system by trying to lstat every single thing that gets returned. (I have
    no idea why it does this, as it returns it whether it exists or not, but
    strace shows that it does indeed do this.)

    Xho

    --
    -------------------- http://NewsReader.Com/ --------------------
    Usenet Newsgroup Service $9.95/Month 30GB
    , Jun 13, 2006
    #6
    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. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,112
    Leor Zolman
    Apr 13, 2004
  2. Alex Vinokur
    Replies:
    2
    Views:
    2,793
    Alex Vinokur
    May 13, 2004
  3. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,279
    DHOLLINGSWORTH2
    Mar 11, 2005
  4. Replies:
    6
    Views:
    464
  5. Seth Leija

    Combinations or Permutations

    Seth Leija, Sep 20, 2010, in forum: Python
    Replies:
    4
    Views:
    271
    Raymond Hettinger
    Sep 21, 2010
Loading...

Share This Page