2

次の問題があります。n 個の要素のセット S が与えられた場合、サイズ k=1,2,...,m の順序を無視して、可能な組み合わせをすべて繰り返し生成する必要があります。

例：

n =3
S = {1,2,3}

考えられるすべての組み合わせは次のとおりです。

k=1: 1,2,3

k=2: 11, 12, 13, 22, 23, 33

k=3: 111, 112, 113, 122, 123, 133, 222, 223, 233, 333.

k=4: 1111, 1112, 1113, ...

...

k=m: ...

明らかに、ステップ k での組み合わせは、k-1 で得られた組み合わせを使用して計算できます。すべての k のすべての組み合わせを取得するための最適なアルゴリズム (疑似コード) とその複雑さは何ですか?

4

2 に答える 2

0

この質問に答える最も自然な方法は、再帰を使用することだと思います。

これを解決する本当の「良い」方法はありません。これは、^ n ランタイムを提供する順列のそれぞれを通過する必要があるためです。Javaを使用して同様の問題を抱えたこの例をネットで見つけました。同じように機能しますが、int の配列の代わりに文字列を使用します。かなり簡単に変換できるはずです。

public class MainClass {
  public static void main(String args[]) {
    permuteString("", "String");
  }

  public static void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1)
      System.out.println(beginningString + endingString);
    else
      for (int i = 0; i < endingString.length(); i++) {
        try {
          String newString = endingString.substring(0, i) + endingString.substring(i + 1);

          permuteString(beginningString + endingString.charAt(i), newString);
        } catch (StringIndexOutOfBoundsException exception) {
          exception.printStackTrace();
        }
      }
  }
}

String.Repeat(n) を簡単に追加して、問題のさまざまなサイズのコンポーネントを再作成できます。

于 2012-09-10T01:04:37.573 に答える
0

コードで本当に必要なものに基づいて、2 つのアプローチを試すことができます。要素の数が非常に多くなる可能性があるため、アプローチ 1 は実行できない場合があります。アプローチ 2 は、アプリケーションにとって十分な可能性があるすべてのソリューションを反復します。

アプローチ 1: すべての組み合わせを再帰的に生成する

すべての要素の順序付きセットから始めます (例では 1..n)。このセットには、長さ 1 のすべての組み合わせが含まれます。

次に、長さ 1 のすべての組み合わせを含む新しいセットを作成します。前のセットの要素を取得し、最後の要素以上のすべての可能な他の要素を追加して、これを埋めます。たとえば、セットから要素 1 を取得する場合、要素 11、12、13、...1n を取得するには、それに 1..n を追加します。要素 3 を取得する場合は、要素 33、34、...3n を取得するために 3..n のみを追加します。この手順を k 回繰り返して、長さ k のシーケンスを取得します。

アプローチ 2: 組み合わせを繰り返す

セットは非常に大きくなる可能性があり、すべてのソリューションを反復することができます。長さ k のすべての組み合わせが必要だとします。

  1. 長さ k のベクトルを作成し、最初の要素の k 倍 (k=4 の場合は 1111) で埋めます。

  2. 最後の要素を後続の要素に置き換えて、新しい組み合わせ (1112) を作成します。最後の要素がすでにセット内の最大の要素 (n) である場合は、それを最初の要素に設定し、最後の要素から 2 番目の要素を増やします。2 つの要素 (1 と 2) のセットの場合、1112 の後継は 1121 になります。これを再帰的に追加します。

これは、長さ k のすべての組み合わせをループします。より短い長さの組み合わせも必要な場合は、ベクトルの最初の部分を見て見つけることができます。例では、111 から始まり、最後の要素が再び 1 になると、長さ (k-1) の新しい組み合わせが見つかります (=112)。

于 2012-09-10T22:39:14.380 に答える