Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Perl Misc (http://www.velocityreviews.com/forums/f67-perl-misc.html)
-   -   Permutations/combinations from multiple arrays (http://www.velocityreviews.com/forums/t898510-permutations-combinations-from-multiple-arrays.html)

 Peter Ensch 06-13-2006 04:26 PM

Permutations/combinations from multiple arrays

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,
pensch@ti.com A-1140 (214) 480 2333
^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^

 xhoster@gmail.com 06-13-2006 04:56 PM

Re: Permutations/combinations from multiple arrays

Peter Ensch <pensch@ti.com> 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 06-13-2006 05:14 PM

Re: Permutations/combinations from multiple arrays

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 06-13-2006 06:09 PM

Re: Permutations/combinations from multiple arrays

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,
> pensch@ti.com 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 06-13-2006 09:19 PM

Re: Permutations/combinations from multiple arrays

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 06-13-2006 09:45 PM

Re: Permutations/combinations from multiple arrays

"John W. Krahn" <krahnj@telus.net> 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

--