11

数字の2つのグループがあるとしましょう：

{1, 2, 3},
{4, 5}

次の 6 つの組み合わせを出力するアルゴリズムを (Java で) 作成したいと思います。

1,4
1,5
2,4
2,5
3,4
3,5

任意の数のグループと、各グループ内の任意の数のメンバーが存在できます。上記の例では、2 つのグループがあり、最初のグループには 3 人のメンバーがいて、2 番目のグループには 2 人のメンバーがいます。別の例は次のとおりです (3 つのグループ、最初のグループに 3 人のメンバー、2 番目と 3 番目のグループに 2 人のメンバー):

{1, 2, 3},
{4, 5},
{6, 7}

これにより、次の 12 の組み合わせが生成されます。

1,4,6
1,4,7
1,5,6
1,5,7

2,4,6
2,4,7
2,5,6
2,5,7

3,4,6
3,4,7
3,5,6
3,5,7

Javaでこれを行うにはどうすればよいですか? 再帰を使用しようとしていますが、すでに同様の質問を見てきましたが、まだ不足しています。助けてくれてありがとう！（PSこれは宿題のためではありません）

4

5 に答える 5

16

少し退屈して、試してみることにしました。まさにあなたが必要とするものでなければなりません：

public static void main(String args[]) {
    ArrayList<int[]> input = new ArrayList<int[]>();
    input.add(new int[]{1, 2, 3});
    input.add(new int[]{4, 5});
    input.add(new int[]{6, 7});

    combine(input, new int[input.size()], 0);
}

private static void combine(ArrayList<int[]> input, int[] current, int k) {
    if (k == input.size()) {
        for (int i = 0; i < k; i++) {
            System.out.print(current[i] + " ");
        }
        System.out.println();
    } else {
        for (int j = 0; j < input.get(k).length; j++) {
            current[k] = input.get(k)[j];
            combine(input, current, k + 1);
        }
    }
}
于 2012-04-21T19:45:14.960 に答える
9

ライブラリを使用できる場合、グアバ Sets.cartesianProduct(List<Set<E>>)はまさにあなたが探していることを行います。（開示：私はGuavaに貢献しています。）

于 2012-04-21T19:49:55.000 に答える
6

考えられるアプローチの1つ（必ずしも最も効率的とは限りません）は、分割統治アプローチを採用することです。2つのグループのすべての順列を見つけるのは比較的簡単です（最もばかげた方法は、ループに対してネストされているだけです）。と呼ばれる関数を記述permuteしpermute(A,B)、A（たとえば、{（1）、（2）、（3）}）とB（たとえば、{（4）、（5）}は数値のグループであり、すべてを返す）を実行するとします。単一グループとしてのAとBの順列（例：{（1,4）、（1,5）、（2,4）、（2,5）、（3,4）、（3,5）}） 。

したがって、2つではなくN個のグループがある場合、最も簡単な方法は、問題のごく一部をピックオフすることです。グループA、B、Cがあるとします。これらすべてを個別に心配するのではなく、次のように考えることができます。

permute(permute(A,B),C)

最初にAとBのすべての順列を見つけます。その結果が得られたら、Cでその結果のすべての順列を見つけます。4つのグループA、B、C、Dは次のようになります。

permute(permute(permute(A,B),C),D)

等々。途中の各ステップで、現在の順列結果を取得し、入力として取得したグループのリスト内の次のグループで順列を並べ替えます。一度に2つのグループを組み合わせるだけなので、入力として取得するグループの数に応じてアルゴリズムを変更する必要はありません。

再帰を行う場合、答える必要のあるいくつかの主要な質問があります。

  1. 問題をより小さく、より解決可能な問題に再帰的に分解できますか？上記の例は、あなたができることを証明していると思います。

  2. 基本ケースは何ですか？再帰を停止して巻き戻す原因となる解決策は何ですか？それは一般的に、あなたの再帰がうまくいくことができる本当に単純なものでなければなりません。permute(A,{})この場合、おそらく{}が空集合であるようなものになります。

  3. 再帰的なケースとは何ですか？問題のチャンクをどのように分割し、問題のより小さなサブセットで再発しますか？最初の説明は、これを行う可能性のある1つの方法を示していると思います。一度に1つのグループを分割し、成長し続ける結果でそれを並べ替えるだけです。

この問題には確かに他の解決策があります、これは私の頭に浮かんだ最初のものです。Nがどんどん大きくなると、このアルゴリズムはあまり効率的ではないため、非常に遅くなります。

したがって、このソリューションを使用しなくても、正しい方向に進むことを願っています。

于 2012-04-21T19:32:08.053 に答える
1

次の擬似コードはどうですか（再帰なし）

// Create the initial result filled with the first set of numbers
List result = new List()
For each number in the first set
   result.add(new List(number))

// Iterate over the following sets to permutate over
For each remaining set S
   List newResult = new List()
   For each list L in result
     For each number N in S
       newResult.add(copy of L with N added)
   result = newResult
于 2012-04-21T19:38:26.007 に答える