[FWP] Cartesian Cross-Products

[Jeff Pinyan <jeffp@crusoe.net>]

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.)

I thought "hmm, that's a bit of a poser."  After just thinking up some
approaches, I suddenly hit upon one at a group meeting for another one of
my classes, at 11:00 PM.  In 20 minutes, I'd perfected it:

### PERL CODE TO FOLLOW ###

=pod Explanation of algorithm used

Given a list of sets, say ([a,b], [c,d,e], [f,g]), we first determine how
many sets can be created.  Mathematically, this is determined as follows:

  For a list of sets, { a[1], a[2], ..., a[n] }, to determine how many sets
  can be created by choosing an element from a[1] as the first element of a
  set, an element of a[2] for the second element, and so on, picking an
  element of a[n] as the n-th element, we create a list { s[1], s[2], ...,
  s[n] }, where each element s[i] is the number of element in a[i].  We can
  pick any of the s[i] elements from a[i] for the specified element in the
  set to be created, so the number of sets to be created is

      n
    -----
     | |   s[p]  .
     | |
     p=1

  That is, the product of the sizes of all the sets.

Now that we know how many sets we'll be creating, we start to populate these
sets.  We modify the same index of each set per loop; that is, we modify
a[0][0], a[1][0], a[2][0], ..., a[n][0], before we modify any index in a[1].

I utilize a "repetition value", which starts at 1, and is multiplied by the
size of the previous set (s[i-1]) when the population of a specific index of
the new sets is complete.  The repetition value indicates how many times the
specific element will be inserted in a row on a pass over an index.  The
starting value of 1 means that each element in a[0] will be inserted once, and
then the next element will be entered, and after all elements have been
exhausted, we go back to inserting a[0].

After we've exhausted a[0], we multiply the repetition value by s[0], and we
move on to a[1].  For each value here, we fill in the next index in the new
sets, but we do this R times in succession, where R is the repetition value.

We continue through until the new sets are completed.

=cut

  sub cartesian {
    my $len = 1;
    my (@ret,$rep,$i,$j,$p,$k);

    for (@_) { $len *= @$_ }

    for ($rep = 1, $i = 0; $i < @_; $rep *= @{ $_[$i] }, $i++) {
      for ($j = 0, $p = 0; $j < $len; $j += $rep, $p++) {
        for ($k = 0; $k < $rep; $k++) {
          print STDERR << "DEBUGGING" if 0;  # set to true to see debug output
repetition value: $rep
modifying set[@{[ $j + $k]}], index[$i]
value is element @{[ $p % @{ $_[$i] } ]} ('$_[$i][$p % @{ $_[$i] }]') of original set[$i]

DEBUGGING
          $ret[$j + $k][$i] = $_[$i][$p % @{ $_[$i] }]
        }
      }
    }

    return @ret;
  }

  # uncomment to see a test run
  # print map "@$_\n", cartesian( [1,2] , [3,4,5] , [6,7] );

__END__

-- 
MIDN 4/C PINYAN, NROTCURPI, US Naval Reserve             japhy@pobox.com
http://www.pobox.com/~japhy/                  http://pinyaj.stu.rpi.edu/
PerlMonth - An Online Perl Magazine            http://www.perlmonth.com/
The Perl Archive - Articles, Forums, etc.    http://www.perlarchive.com/


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