Velocity Reviews > Perl > Permutations/combinations from multiple arrays

# Permutations/combinations from multiple arrays

Peter Ensch
Guest
Posts: n/a

 06-13-2006
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,
http://www.velocityreviews.com/forums/(E-Mail Removed) A-1140 (214) 480 2333
^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^

xhoster@gmail.com
Guest
Posts: n/a

 06-13-2006
Peter Ensch <(E-Mail Removed)> 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!

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB

Brian McCauley
Guest
Posts: n/a

 06-13-2006

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 ];
}

charley@pulsenet.com
Guest
Posts: n/a

 06-13-2006

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,
> (E-Mail Removed) 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

John W. Krahn
Guest
Posts: n/a

 06-13-2006
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

xhoster@gmail.com
Guest
Posts: n/a

 06-13-2006
"John W. Krahn" <(E-Mail Removed)> 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

--
Usenet Newsgroup Service \$9.95/Month 30GB