2

組み合わせ論と列挙についてたくさんの質問があることは承知していますが、私が探しているものに特に関連するものは何も見つかりませんでした。私が何かを見逃した場合は、それを指摘してください。質問を閉じることができます.

したがって、N 個の要素のセットがあり、Sum(k1,...,kx) <= N である x 個の正の整数 k1,...,kx があると仮定します。選択できるすべての方法を列挙したいと思います (置換なし) N の元のセットから、指定されたサイズの x サブセット。

私はそれを正しく表現したことを願っています。そうでない場合に備えて、簡単な例を示します。
N = 4、x = 2、k1 = 2、k2 = 1。

列挙する必要があります

  • {1, 2} {3}
  • {1, 2} {4}
  • {1, 3} {2}
  • {1, 3} {4}
  • {1, 4} {2}
  • {1, 4} {3}
  • {2, 3} {1}
  • {2, 3} {4}
  • {2, 4} {1}
  • {2, 4} {3}
  • {3, 4} {1}
  • {3, 4} {2}

一般的なケースでは、合計数は次のようになります。

C(N, k1) * C(N - k1, k2) * ... * C(N - Sum(k1,...,kn-1), kn)。

私の最初の推測では、これはスタックを使用してかなり簡単に実行できるということです。各スタック レベル i で、標準的な組み合わせの列挙を使用してサブセット ki が生成されます。各レベルで選択された要素をソース セットから削除するか、元のセットから列挙して、要素が以前に含まれていた場合をスキップします。 .

私の質問は、より高速でエレガントなソリューションはありますか?

4

1 に答える 1

2

あなたの質問は、まさにマルチセットの順列を列挙する問題です。(あなたの k iが順序付けられていると仮定します)。

まず、この問題は Σk = N の場合とまったく同じであることに注意してください。なぜなら、Σk < N の場合、値が N - Σk であるk x+1を単純に追加できるからです。

ここで、元のセット S の要素を任意の固定順序で配置し、k 1 1、k 2 2、k 3 3、... k x xで構成されるマルチセットの各順列を生成します。k iの合計が N になるため、このマルチセットは S と同じサイズ (N) になります。 S の各要素を、インデックスがマルチセットの順列の対応する値であるサブセットに割り当てることによって、S のパーティションを作成します。 .

たとえば、S = {りんご、バナナ、ちりもや、日付} (N = 4)。k 1 = 2 と k 2 = 1を取り、k 3 = 1を追加して合計を 4 にします (サブセット 3 に割り当てられた要素は無視します)。ここで、マルチセットの順列を列挙します1 1 2 3(k に対応する 2 つの 1、1 つの 2、および 1 つの 3 があります)。

1 1 2 3    1 2 3 1    2 1 1 3    3 1 1 2
1 1 3 2    1 3 1 2    2 1 3 1    3 1 2 1
1 2 1 3    1 3 1 1    2 3 1 1    3 2 1 1

これらを S の分割に変換し直します。たとえば、次のようにし1 3 1 2ます。

apple     1 -> subset 1
banana    3 -> unused
chirimoya 1 -> subset 1
date      2 -> subset 2

だから私たちは持っています{{apple, chirimoya}, {date}}

セットの順列を見つけるための標準アルゴリズムは、マルチセットでも同様に機能しますが、マルチセットに多くの重複がある場合は最適ではありません。

于 2012-10-22T16:21:40.390 に答える