2

これらのタイプのアルゴリズムの言語（つまり、これをグーグルで検索する方法）がよくわからないので、探しているものを示します。

私は3つの配列を持っています（ソース配列は同じ長さではありません）：

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

これらの配列のすべての可能な組み合わせが必要です。

  • 各ソース配列から取得される要素は1つだけです。
  • 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で動作しますが、同様の言語または擬似コードはもちろん問題ありません。または、どの特定のタイプの順列/組み合わせアルゴリズムを検討する必要があるかについてのヒントを取得します。

4

2 に答える 2

2

これらはデカルト積だと思います。それらを生成するのは非常に簡単です。

  • 固定数の配列の場合 (Perl の場合):

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

  • @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 番目の方法では、さらに簡単です。結果に@partialandmap { [$_] } @An_plus_1を追加するだけです (または、英語では、 の部分デカルト積とA1 x ... x An、新しいセットの要素から作成された単一の要素セットから生じるすべてのセット)。

于 2012-04-05T00:27:09.000 に答える
0

RBarryYoung のヒントを使用すると、これがそれらを生成する最短の方法であり、bash (および sed、D、w、および 4 を削除する) です。

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

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

もう 1 つの簡単な方法は SQL で、デフォルトで実行されます。

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

テーブルに 'A,B,C, ,' と 'x,y,z, ,' と '1,2,3, ' のみが含まれている場合は、はるかに短くなります。

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

デカルト積のほかに、この組み合わせの別の言葉はクロス積です。

リスト/シーケンス/その他のコレクションの不明な数の不明なサイズについては、イテレータをお勧めします-PHPにそのようなものがある場合。以下は 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' と ' ' を削除できます。

于 2012-04-05T01:32:39.090 に答える