Re: Cartesian Cross-Products

[Anonymous Monk]

Add "$#ret = $len -1" at line 64 for better performance. For a 100*65*20 set, benchmark results are: Benchmark: timing 10 iterations of new, old... new: 16 wallclock secs (15.59 usr + 0.09 sys = 15.68 CPU) @ 0.64/s (n=10) old: 21 wallclock secs (20.16 usr + 0.10 sys = 20.26 CPU) @ 0.49/s (n=10)

[Anonymous Monk]

People who learned C should "learn" Perl... This is the "Perl" way to do it.

perl -e '
use strict;

my @a=qw{1 2 3};
my @b=qw{4 5};
my @c=();
foreach my $a (@a) {
  foreach my $b (@b) {
    push @c, [$a, $b];
  }
}
print join("\n", map {join ",", @$_} @c), "\n"
'

---
1,4
1,5
2,4
2,5
3,4
3,5

Mike (mrdvt92)

[waba]

It is indeed the Perl way to do it if you know in advance how many arrays you'd like to get the product of.

If you don't, Japhy's algorithm is the way to go - even if it looks C-ish with a lot of indices. I suspect that it may be faster as well, using the array pre-allocation optimisation pointed out earlier.

[Anonymous Monk]

"The Perl Way"

sub cartesian {
    my @C = map { [ $_ ] } @{ shift @_ };

    foreach (@_) {
        my @A = @$_;

        @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A;
    }

    return @C;
}

[saenns]

Hi, Perl n00b here. Check out my recursive solution for any number of sets. Feel the scheme.

sub cartesian {
    my @sets = @_;
    # base case
    if (@sets == 0) {
        return ([]);
    }
    my @first = @{@sets[0]};
    # recursive call
    shift @sets;
    my @rest = cartesian(@sets);
    my @result = ();
    foreach my $element (@first) { 
        foreach my $product (@rest) { 
            my @newSet = @{$product};
            unshift (@newSet, $element);
            push (@result, \@newSet);
        }
    }
    return @result;
}

[Anonymous Monk]

That

  my @C = map { [ $_ ] } @{ shift @_ };

Can be simplified to:

  my @C = [];

Don't believe me? Try it. Also, it now works correctly in the case you pass no arguments to the function. This may be a matter of taste, but I prefer the leftmost array to be the outermost loop. So that leaves us with:

sub cartesian {
    my @C = [];

    foreach (reverse @_) {
        my @A = @$_;

        @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A;
    }

    return @C;
}