Efficiently process all possible 2D array combinations in Perl

Question

I have a 2D array containing numbers. I am attempting to work out the product of multiplying a single number from each sub-array with one from each of the other sub-arrays; I then need to do this for all possible combinations.

The aim is that I input a file of the frequency of individual events, and get an output of the probability of a particular series of these events happening, with one event from each set.

I have fudged together some code with the help of a previous question:

for my $aref ( getCartesian(@freq) ) {
    my $p = 1;
    foreach my $n (@$aref) {
        $p = $p * $n;
    }
    print "$p\n";
}


sub getCartesian {
    my @input = @_;
    my @ret = map [$_], @{ shift @input };

    for my $a2 (@input) {
        @ret = map {
            my $v = $_;
            map [@$v, $_], @$a2;
        }
        @ret;
    }
    return @ret;
}

where @freq is an array of arrays, such as:

@freq = [0.1, 0.2, 0.3,]
        [0.4, 0.5, 0.6,]
        [0.7, 0.8, 0.9,]; `and ~ 20 more sub arrays`

This works fine for a small test file, but when I give it my required input of 24 sub-arrays with 3 items each, the generation of combinations is clearly far too intensive, with 3^24 possibilities. I have run it on a machine with 22 GB RAM, and it maxed out after 4 minutes before any output.

My question is, how could I modify the code so that I can print out $p for each combination, without having to hold the whole set of combinations in memory, which kills it. I presume that time would be the only limiting factor for computation then, not resources.

Edit: a method in base Perl without packages would be great. I don't have admin on the HPC facility sadly,

Answer 1

Set::CrossProduct lets you iterate through the Cartesian product so you don't have to store everything in memory:

use List::Util qw(reduce);
use Set::CrossProduct;

my @array = (
    [0.1, 0.2, 0.3],
    [0.4, 0.5, 0.6],
    [0.7, 0.8, 0.9]
);

my $iterator = Set::CrossProduct->new(\@array);
while (my $tuple = $iterator->get) {
    say '(', join(', ', @$tuple), '): ', reduce { $a * $b } @$tuple;
}

Outputs:

(0.1, 0.4, 0.7): 0.028
(0.1, 0.4, 0.8): 0.032
(0.1, 0.4, 0.9): 0.036
(0.1, 0.5, 0.7): 0.035
(0.1, 0.5, 0.8): 0.04
(0.1, 0.5, 0.9): 0.045
(0.1, 0.6, 0.7): 0.042
(0.1, 0.6, 0.8): 0.048
(0.1, 0.6, 0.9): 0.054
(0.2, 0.4, 0.7): 0.056
(0.2, 0.4, 0.8): 0.064
(0.2, 0.4, 0.9): 0.072
(0.2, 0.5, 0.7): 0.07
(0.2, 0.5, 0.8): 0.08
(0.2, 0.5, 0.9): 0.09
(0.2, 0.6, 0.7): 0.084
(0.2, 0.6, 0.8): 0.096
(0.2, 0.6, 0.9): 0.108
(0.3, 0.4, 0.7): 0.084
(0.3, 0.4, 0.8): 0.096
(0.3, 0.4, 0.9): 0.108
(0.3, 0.5, 0.7): 0.105
(0.3, 0.5, 0.8): 0.12
(0.3, 0.5, 0.9): 0.135
(0.3, 0.6, 0.7): 0.126
(0.3, 0.6, 0.8): 0.144
(0.3, 0.6, 0.9): 0.162