Permutations/combinations from multiple arrays

[Peter Ensch]

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 address removed) A-1140 (214) 480 2333
^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^

 

[xhoster]

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

 

[Brian McCauley]

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]

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 address 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]

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

 

[xhoster]

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