（順序を維持しながら）デカルト/組み合わせアルゴリズム

Question

私はかなりのアルゴリズム（すなわち、これをGoogleにどのように）、これらのタイプの言語を知らないので、私はちょうど私が探しているものを説明します：

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

Iは、これらの配列のすべての可能な組み合わせたい：各ソース・アレイから

• 1個以下の要素が取られるが、私は3つのアレイを（ソース列が等しくない長さである）を有します。
• array1、array2、array3の順番は決して壊れません（ABCはいつもxyzの前に来て、いつも123の前に来ます）。

だから、結果は次のようになります。

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'), 
); 

結果の順序は私には関係ありません。

phpで作業しますが、類似の言語または疑似コードは当然です。または、私はちょうど私が見ていなければならない順列/組み合わせアルゴリズムの特定のタイプについてのヒントを取るでしょう。

Answer 1

私はこれらがデカルト製品であると言います。それらを生成することは非常に簡単です。

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

一般的手順：（Perlで）アレイの固定された数の

• @partialを想定は、A1 x A2 x ... x Anのデカルト積の配列であり、我々はA1 x ... x An x An+1

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

  これを望ん明らかにすべての配列に対して反復処理を行う必要があります。

ここで、セットのいくつかの要素を省略したい場合は、少しだけひねります。最初の方法では、配列のそれぞれに別の要素を追加するだけです（undefは明らかですが、何でもできます）。そして、結果セットのこれらの要素をフィルタリングして除外します。 2番目の方法ではさらに簡単です：@partialとmap { [$_] } @An_plus_1を結果に加えてください（英語では、部分デカルト積から得られたすべてのセットはA1 x ... x Anとなり、新しいセットの要素から作られた単一の要素セットに加えて） 。RBarryYoungのヒントと

Answer 2

、これは最短それらを製造する方法は、bash（そしてsedは、Dを除去するため、W、及び4）：

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

A1 A2 A3 A Ax1をAx2をAX3アックスAY1 AY2 AY3 AyのAZ1 AZ2 AZ3アリゾナ B1とB2とB3 B BX1 BX2 BX3 BxをBY1、BY2 BY3によりBZ1 BZ2 BZ3のBz C1 C2 C3 C Cx1乃至CX2、CX3 CxのCY1 Cy 2はCy3のサイCZ1 CZ2 CZ3 Czを 1 2 3×1×2×3のX、Y1 y2 y3 y z1 z2 z3 z

別の簡単な方法'A、B、C、' と 'X、Y、Z、' と '1,2,3、' あなたのテーブルが含まれている場合のみ

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

を：、デフォルトでそれをしないSQL、ありますこの組み合わせは外積であるため、直積の横に、

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

別の単語：それははるかに短いです。

リスト/シーケンス/その他のコレクションの未知のサイズが不明な場合は、PHPにこのようなことがある場合はIteratorをお勧めします。ここでは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) 

ラッパーは出力から「0」と「」を除去するのに使用することができます。