# Permutations/combinations from multiple arrays

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

1. ### Peter EnschGuest

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

2. ### 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!

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB
, Jun 13, 2006

3. ### Brian McCauleyGuest

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
4. ### 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
5. ### John W. KrahnGuest

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
6. ### 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

--
Usenet Newsgroup Service \$9.95/Month 30GB
, Jun 13, 2006