Re: [FWP] Cartesian Cross-Products

[Ariel Scolnicov <ariels@compugen.co.il>]

Jeff Pinyan <jeffp@crusoe.net> writes:

> I was working on a Programming in Perl quiz for a college course I'm
> taking (for the credit) and being a teacher's assistant for (for the
> money, and for the fun).  One question was:
> 
>   Write a subroutine that returns the Cartesian cross product of a set of
>   sets, where each set is represented by a single array.  Thus, the sub
>   should take an arbitrary number of arrays (i.e. refs to arrays) and
>   return an arbitrary number of arrays.  You may assume that it will never
>   be called in scalar context.  (Remember that the Cartesian cross product
>   of n sets is the set of all possible n-tuples (ordered sets of size
>   n) whose first element is from the first of the n sets, the second
>   element is from the second of the n sets, etc.)

Why not pretend Perl is a functional language, and use map?

Tested on the single example in the code:

................................ cutcutcut ................................
#!/usr/local/bin/perl -w

use strict;

sub cross {
  if (@_) {
    my @vec = @{$_[0]};
    shift;
    my @cross = cross(@_);
    map { my $x=$_; map { [$x, @{$_}] } @cross } @vec;
  }
  else {
    ([]);
  }
}

map { print "@{$_}\n" } cross ([1,2],[3,4,5],[6,7,8,9]);
................................ cutcutcut ................................


[...]

PS. A similar algorithm to yours works for generating all permutations 
on {1,...,n}: just count from 0 to n!-1, and use the numbers' variadic 
base representation (1st digit is 2's, 2nd is 3's, ...).

-- 
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            |ariels@compugen.co.il
Compugen Ltd.          |Tel: +972-2-6795059 (Jerusalem)	\ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658514 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe