alkis has asked for the wisdom of the Perl Monks concerning the following question:

hi monks ,i seek for some wisdom... my script generates a list of lists with number like these below: 
list[1]=[1,2,6]
list[2]=[4,5]
list[3]=[7,3]

[download]
as you see there is not standart number of elements in each list,although elements cannot be repeated... what i want to do is to take these lists and create all the possible combinations of these numbers... for example if i have the above lists there can be created 12 possible lists with the combination of these numbers, which are: 
comb[1]=[1,4,7]
comb[2]=[1,4,3]
comb[3]=[1,5,7]
comb[4]=[1,5,3]
comb[5]=[2,4,7]
comb[6]=[2,4,3]
comb[7]=[2,5,7]
comb[8]=[2,5,3]
comb[9]=[6,4,7]
comb[10]=[6,4,3]
comb[11]=[6,5,7]
comb[12]=[6,5,3]

[download]
the number of elements in each comb[] list is equal to the number of lists (in this example 3), and in each comb[] eixsts one element of each list[] at a time... the question is how can i do that in perl??? thank you alkis

Replies are listed 'Best First'.
Re: combine elements of lists
by Corion (Patriarch) on Apr 22, 2008 at 13:14 UTC
[reply]
Re: combine elements of lists
by jdporter (Paladin) on Apr 22, 2008 at 14:34 UTC

    It's very easy to implement using recursion. 

    my @list;
$list[0]=[1,2,6];
$list[1]=[4,5];
$list[2]=[7,3];

sub combin
{
    @_ or return [];
    my $l = shift;
    map
    {
        my $n = $_;
        map { [ $n, @$_ ] } combin(@_)
    }
    @$l
}

my @comb = combin(@list);

print "@$_\n" for @comb;

    [download]

    Similar to how I did it another time.

    And the functionality is available in a module, Set::CrossProduct.

    A word spoken in Mind will reach its own level, in the objective world, by its own weight
[reply]
[d/l]
Re: combine elements of lists
by mscharrer (Hermit) on Apr 22, 2008 at 13:27 UTC
    For this example you could write: 
    my %list;
$list[1]=[1,2,6];
$list[2]=[4,5];
$list[3]=[7,3];

my $n = 1;
foreach my $A (@{$list[1]}) {
    foreach my $B (@{$list[2]}) {
        foreach my $C (@{$list[3]}) {
            print "comb[$n] = [$A,$B,$C]\n";
            $n++;
        }
    }
}

    [download]
    You now have to generalize this using a loop.
[reply]
[d/l]
      I know implemented some general loop for your problem. A index array is used to remember which index of which array is currently taken. In every iteration the index of the first array is incremented and wrapped around to zero if got to big. In this case the second index is incremented, and so forth...

      The resulting order is combinations is here in different, but this could be fixed by changing the order of index incrementation. 

      my @lists = (
    [1,2,6],
    [4,5],
    [7,3],
);

# Init indexes to zero
my @idx = map { 0 } (0..$#lists);

my $n = 0;

COMP:
while (1) {
    $n++;
    print "comp[$n] = [";
    # Join all list elements given by index array
    print join ',', map { $lists[$_][$idx[$_]] } (0..$#lists);
    print "]\n";

    # Increment lowest index, handle overrun
    INDEX:
    foreach my $i (0..$#lists) {
       $idx[$i]++;
       # If new index greater then highest index
       if ($idx[$i] > $#{$lists[$i]}) {
           # Wrap around
           $idx[$i] = 0;
           if ($i == $#lists) {
               # Stop outher loop if last index overruns
               last COMP;
           }
       }
       else {
           # stop if no overrun occured
           last INDEX;
       }
   }
}

__END__
comp[1] = [1,4,7]
comp[2] = [2,4,7]
comp[3] = [6,4,7]
comp[4] = [1,5,7]
comp[5] = [2,5,7]
comp[6] = [6,5,7]
comp[7] = [1,4,3]
comp[8] = [2,4,3]
comp[9] = [6,4,3]
comp[10] = [1,5,3]
comp[11] = [2,5,3]
comp[12] = [6,5,3]

      [download]
      Update: To get the same order like in your example add/change the following: 
      22a23
>        $i = $#lists - $i;
28c29
<            if ($i == $#lists) {
---
>            if ($i == 0) {

      [download]
      e.g. add the first line after the INDEX foreach loop line and change the if statement like shown.
[reply]
[d/l]
[select]
      mscharrer this is about something i have thought to do, but how can i generalize it? i dont know a priori how many lists will be created, it depends on the input...there might be 1 or 2 or 3 or more...
[reply]
Re: combine elements of lists
by grizzley (Chaplain) on Apr 22, 2008 at 13:02 UTC
[reply]
[d/l]

Back to Seekers of Perl Wisdom