CODEWITHSUNDEEP
algorithmcombinationscartesian-product
ack
ack

Reputation: 14935

Cartesian/combination algorithm (while maintaining order)

Since I don't quite know the language of these types of algorithms (i.e. how to google this), I'll just demonstrate what I'm looking for:

I have a three arrays (source arrays are of not equal lengths):

$array1 = array('A', 'B', 'C', 'D');
$array2 = array('x', 'y', 'z');
$array3 = array('1', '2', '3');

I would like all possible combinations of these arrays where:

So the result would be:

array(
  array('A', 'x', '1'),
  array('A', 'x', '2'),
  array('A', 'x', '3'),
  array('A', 'y', '1'),
  // etc ...

  // But I also need all the partial sets, as long as the rule about
  // ordering isn't broken i.e.:
  array('B'),
  array('B', 'x'),
  array('B', 'x', '1'),
  array('x'),
  array('x', '1'),
  array('1'),
);

The order of the results doesn't matter to me.

Working in php, but similar language or pseudo code is fine of course. Or I'd just take a tip on what specific types of permutation/combination algorithms I should be looking at.

Upvotes: 2

Views: 1277

Answers (2)

user unknown
user unknown

Reputation: 36229

With RBarryYoung's hint, this is the shortest way to produce them, bash (and sed, to remove D, w, and 4):

echo {A..D}{w..z}{1..4} | sed 's/[Dw4]//g'

A1 A2 A3 A Ax1 Ax2 Ax3 Ax Ay1 Ay2 Ay3 Ay Az1 Az2 Az3 Az B1 B2 B3 B Bx1 Bx2 Bx3 Bx By1 By2 By3 By Bz1 Bz2 Bz3 Bz C1 C2 C3 C Cx1 Cx2 Cx3 Cx Cy1 Cy2 Cy3 Cy Cz1 Cz2 Cz3 Cz 1 2 3 x1 x2 x3 x y1 y2 y3 y z1 z2 z3 z

Another, easy way, is SQL, which does it by default: 

SELECT upper, lower, num 
FROM uppers, lowers, numbers
WHERE upper in ('A', 'B', 'C', ' ')
AND lower in (' ', 'x', 'y', 'z')
AND (number in (1, 2, 3) OR number IS NULL);

If your tables only contain 'A,B,C, ,' and 'x,y,z, ,' and '1,2,3, ' it is much shorter: 

SELECT upper, lower, num 
FROM uppers, lowers, numbers;

Another word, beside cartesian product, for this combinations is cross product.

For an unknown number of unknown size of Lists/Sequences/other collections, I would recommend an Iterator - if PHP has such things. Here is an implementation in Scala: 

  class CartesianIterator (val ll: Seq[Seq[_]]) extends Iterator [Seq[_]] {
    var current = 0
    def size = ll.map (_.size).product
    lazy val last: Int = len

    def get (n: Int, lili: Seq[Seq[_]]): List[_] = lili.length match {
      case 0 => List () 
      case _ => {
        val inner = lili.head 
        inner (n % inner.size) :: get (n / inner.size, lili.tail) 
      }
    }

    override def hasNext () : Boolean = current != last
    override def next (): Seq[_] = {
      current += 1
      get (current - 1, ll) 
    }
  }

  val ci = new CartesianIterator (List(List ('A', 'B', 'C', 'D', ' '), List ('x', 'y', 'z', ' '), List (1, 2, 3, 0)))
  for (c <- ci) println (c)

List(A, x, 1)
List(B, x, 1)
List(C, x, 1)
List(D, x, 1)
List( , x, 1)
List(A, y, 1)
List(B, y, 1)
...
List( , z, 0)
List(A,  , 0)
List(B,  , 0)
List(C,  , 0)
List(D,  , 0)
List( ,  , 0)

A wrapper could be used to remove the '0' and ' ' from the output.

Upvotes: 0

jpalecek
jpalecek

Reputation: 47762

I'd say these are Cartesian products. Generating them is quite easy.

  • for fixed number of arrays (in Perl):

    for my $a(@arrayA) {
  for my $b(@arrayB) {
    push @result, [$a, $b];
  }
}

  • general procedure: Assume @partial is an array for Cartesian product of A1 x A2 x ... x An and we want A1 x ... x An x An+1

    for my $a(@partial) {
  for my $b(@An_plus_1) {
    push @result, [@$a, $b];
  }
}

    This would obviously need to iterate over all the arrays.

Now, that you want also to omit some of the elements in the sets, you just twist it a little. In the first method, you can just add another element to each of the arrays (undef is obvious choice, but anything will do) and then filter out these elements in the result sets. In the second method, it is even easier: You just add @partial and map { [$_] } @An_plus_1 to the result (or, in English, all the sets resulting from the partial Cartesian product of A1 x ... x An plus the single element sets made form the elements of the new set).

Upvotes: 2

Related Questions