Algorithm - generating all combinations from items that must be chosen in sequence

Question

I'm looking to find out if a particular algorithm already exists. I want to use it in an application, but I've also seen this come up in several Project Euler problems too.

I'm looking to calculate a specific type of permutation/output set, where the next item chosen must be one from a finite set of options in only the following set.

For example, say I've got 3 arrays

$a1 = array("a", "b", "c");
$a2 = array("d", "e", "f");
$a3 = array("g", "h", "i");

I'm looking to generate all the possibilities of a sequence containing at most 1 element from each array, chosen in order. That is to say as output, I'd like to see:

adg aeg afg
adh aeh afh
adi aei afi

bdg beg bfg 
bdh beh bfh
bdi bei bfi

cdg ceg cfg
cdh ceh cfh
cdi cei cfi

Looking to implement the algorithm in either PHP or Javascript. In essence it will go through a variable number of arrays containing a variable number of elements, and output all of the possiblities of sequences that can occurr in sequential order.

Does this exist?

If so, what is it called? Technically this isnt a permutation or a combination from what I know about both.

EDIT: Daniel Fischer has informed me this is a Cartesian product, here is an implementation taken from the PHP website:

function array_cartesian_product($arrays)
{
    $result = array();
    $arrays = array_values($arrays);
    $sizeIn = sizeof($arrays);
    $size = $sizeIn > 0 ? 1 : 0;
    foreach ($arrays as $array)
        $size = $size * sizeof($array);
    for ($i = 0; $i < $size; $i ++)
    {
        $result[$i] = array();
        for ($j = 0; $j < $sizeIn; $j ++)
            array_push($result[$i], current($arrays[$j]));
        for ($j = ($sizeIn -1); $j >= 0; $j --)
        {
            if (next($arrays[$j]))
                break;
            elseif (isset ($arrays[$j]))
                reset($arrays[$j]);
        }
    }
    return $result;
}

score 2 · Accepted Answer · answered Nov 18 '11 at 01:41

It's a cartesian product, if exactly one item is chosen from each list/array, more precisely a list of the elements of the cartesian product. For lists, it's in Haskell's standard library:

Prelude> sequence ["abc","def","ghi"]
["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh"
,"bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]

I think for PHP or Javascript, you have to code it yourself.

score 0 · Answer 2 · answered Nov 18 '11 at 01:43

You can go through the elements in a loop. For example, you can do the following for your case:

var ret = [];
for (var i=0; i<a1.length; i++) {
  for (var j=0; j<a2.length; j++) {
    for (var k=0; k<a3.length; k++) {
      ret.push( [a1[i], a2[j], a3[k]] );
    }
  }
}
// do stuff with ret

Note though that this is pretty slow, especially if you have lots of arrays of very long arrays. For Project Euler, there is usually some other insight that you can use instead of enumerating everything.

Right, however I'm looking to abstract the concept so that I could run it against a variable number of arrays. — barfoon, Nov 18 '11 at 01:58

score 0 · Answer 3 · answered Nov 18 '11 at 02:00

I think you're right that it's neither a permutation nor a combination because the string-length is fixed in your case. Pardon my use of java [7], but it's the one I currently know best.

public abstract class AFixedPermutation {
   private char[][] fields;
   private StringBuilder sb = new StringBuilder();
   private int[] callvec;
   private int maxDepth;

   public FixedPermutation(char[][] fields) { 
     this.fields = fields; 

     callvec = new int[fields.length];
     for (int i = 0; i < fields.length; i++) callvec[i] = 0;
     maxDepth = callvec.length - 1;
     recurse(0);
   }

   protected abstract emit(String s);

   private void recurse(int depth) {
     for (int i = 0; i < fields[depth].length; i++) { 
        callvec[depth] = i;
        if (depth == maxDepth) { apply(); }
        else {recurse(depth + 1); }
     }
   }

   private void apply() {
      sb.setLength(0);
      for (int i = 0; i < callvec.length; i++) {
        sb.append(fields[i][callvec[i]]);
      }
      emit(sb.toString());
   }
}

score 0 · Answer 4 · answered Nov 18 '11 at 06:58

In Mathematica this is natively implemented as Tuples.

Tuples[{{a, b, c}, {d, e, f}, {g, h, i}}]

{{a, d, g}, {a, d, h}, {a, d, i}, {a, e, g}, {a, e, h}, {a, e, i},
 {a, f, g}, {a, f, h}, {a, f, i}, {b, d, g}, {b, d, h}, {b, d, i},
 {b, e, g}, {b, e, h}, {b, e, i}, {b, f, g}, {b, f, h}, {b, f, i},
 {c, d, g}, {c, d, h}, {c, d, i}, {c, e, g}, {c, e, h}, {c, e, i},
 {c, f, g}, {c, f, h}, {c, f, i}}

It can also be done with Outer (generalized outer product):

Outer[List, {a, b, c}, {d, e, f}, {g, h, i}]

Or with iteration (Table):

Table[{x, y, z},
 {x, {a, b, c}},
 {y, {d, e, f}},
 {z, {g, h, i}}
]

Or with recursion:

sets[{}, c__] := {{c}}
sets[{x_, r___}, c___] := Join @@ (sets[{r}, c, #] & /@ x)

sets[{{a, b, c}, {d, e, f}, {g, h, i}}]

Algorithm - generating all combinations from items that must be chosen in sequence

4 Answers4

Linked