1

長さが異なる配列Uの配列があります。D各セットから1つの要素で構成される異なる順列を選択する配列インデックスのすべての順列を返すことができる必要があります。また、このアルゴリズムは、最後の順列のみを記憶し、get_nextメソッドを使用して次の順列を返すオブジェクトとして表される必要があります。

たとえば、それぞれ3つの要素の長さの順列U = [array_of_size_n1, array_of_size_n2, array_of_size_n3]があります。n1*n2*n3

編集：セットの数も異なります。

4

4 に答える 4

2

Python を使用している場合、これは標準ライブラリの一部です: itertools.product. しかし、そうでないと仮定すると、ここに疑似コード バージョンがあります。

// Create an initialised array of indexes.
int[] index0(arrays) {
    // We require all arrays to be non-empty.
    for a in arrays {
        assert len(a) != 0;
    }
    return new int[len(arrays)];
}

// Increment the indices. Returns false when the indices wrap round to the start.
bool next_index(indices, arrays) {
    for (i = len(indices) - 1; i >= 0; --i) {
        indices[i] += 1
        if indices[i] < len(arrays[i]) {
            return true;
        }
        indices[i] = 0;
    }
    return false;
}

このように使用できます (空の配列がないと仮定します)。この例では、配列の要素のすべての組み合わせを出力します。

indices = index0(arrays); 
{
    for (i = 0; i < len(arrays); ++i) {
        print arrays[i][indices[i]];
    }
    print
} while next_index(indices);
于 2010-02-03T04:34:14.953 に答える
1

各配列の個々の位置のカウンターを保持するだけです。get_next メソッドで、カウンターを 1 つ増やし、配列の長さだけ変更します。次に、前のカウンターが 0 になるたびに次のカウンターを増やします。

if (pos3 == array_of_size_n3 -1)
{
   if (pos2 == size_of_array_2 -1)
   {
       pos1 = (pos1 + 1) % size_of_array_1

   }
   pos2 = (pos2 + 1) % size_of_array_2
}
pos3 = (pos3 + 1) % size_of_array_3

print array1[pos1], array2[pos2], array3[pos3]

編集:配列の数が異なる場合は、位置変数を配列に保持します。むしろそのほうがいいかもしれません。そうすれば、配列自体を参照するのと同じ方法で pos 変数を参照できます。

于 2010-02-03T02:59:23.860 に答える
0

それで...これは簡単ではないのはどうですか？

イテレータが必要です。最後の配列を反復処理する必要があります。その配列の最後に到達したら、最後から 2 番目の配列の現在の位置をインクリメントし、最後の配列の先頭に戻ります。

C#yield return構文を使用した疑似コード:

foreach n1 in a1
    foreach n2 in a2
        foreach n3 in a3
            yield return (n1, n2, n3)

編集: セットの数が異なる場合は、何らかの形式の再帰を使用できます。

function next(list)
    firstArray = list.first
    iterator = iterator(list.rest)
    if !iterator
        foreach i in firstArray
            yield return i
    else
        foreach i in firstArray
            while (iterator.hasNext)
                yield return (i, iterator.next)

長さ 1 のリストが渡されたときの動作を考えてから、長さ 2 のリストの動作を考えて、それが実際に機能することを確認してください。

于 2010-02-03T02:51:39.973 に答える
0

Anon が言ったことを理解するために、それらをループするだけではありません。各配列の最後のインデックスが何であったかを知るために、クラスで状態を維持します。ロジックは同じですが、連続ループでは実行されません。擬似コード ロジックは次のようになります。

get_next()
{
  oldn3 = this.n3;
  oldn2 = this.n2;
  oldn1 = this.n1;

  if(this.n3 == this.a3.Count)
     this.n3 = 0;
  そうしないと
     this.n3++;

  if(oldn3 > this.n3)
    if(this.n2 == this.a2.Count)
      this.n2 = 0;
    そうしないと
      this.n2++;

  if(oldn2 > this.n2)
    if(this.n1 == this.a1.Count)
      this.n1 = 0;
    そうしないと
      this.n1++;

  if(oldn1 > this.n1)
    NO_MORE_PERMS を返します。

  [n1、n2、n3]を返します。  
}

getCurrent()
{
  [n1、n2、n3]を返します。
}
于 2010-02-03T03:00:17.583 に答える