3

私は1つの問題で立ち往生しています：サイズ'n'のグループをサイズ'k'のサブグループに分割するすべての可能な方法を見つけること。（ここでは n％k = 0）

たとえば、セットを{1,2,3,4,5,6}にして、3つのサブグループ（k = 3、n = 6）に分割すると、可能なセットは次のようになります。

a）{1,2,3}、{4,5,6}

b）{1,3,5}、{2,4,6}

c）{1,3,6}、{2,4,5}

d）{1,3,4}、{2,5,6}など...

私がやろうとしたのは、最初にセットからサイズkのすべての組み合わせを見つけることでした。次に、これらの組み合わせをループして、すべての組み合わせをグループ化してサブグループのリストを見つけることができるかどうかを調べます。

しかし、このアプローチでは時間計算量がかなり悪いと思います。この問題に対するより良いアプローチはありますか？

4

3 に答える 3

6

再帰的な方法を使用します。これは、必要なすべてのサブセットを正確に生成するため、最適な実行時間であると思います。

public static void solve(int[] a, int k, int i, List<List<Integer>> subsets) {
    if (i == a.length) {
        for (List<Integer> subset : subsets) {
            System.out.print(subset);               
        }
        System.out.println();
    } else {
        // loop over all subsets and try to put a[i] in
        for (int j = 0; j < subsets.size(); j++) {                 
            if (subsets.get(j).size() < k) {
                // subset j not full
                subsets.get(j).add(a[i]);
                solve(a, k, i+1, subsets); // do recursion
                subsets.get(j).remove((Integer)a[i]);

                if (subsets.get(j).size() == 0) {
                     // don't skip empty subsets, so you won't get duplicates
                     break;
                }                    
            }
        }
    }
}

使用法：

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    int k = 3;

    List<List<Integer>> subsets = new ArrayList<List<Integer>>(a.length / k);
    for (int i = 0; i < a.length / k; i++)
        subsets.add(new ArrayList<Integer>(k));
    solve(a, k, 0, subsets);
}

プリント：

[1, 2, 3][4, 5, 6]
[1, 2, 4][3, 5, 6]
[1, 2, 5][3, 4, 6]
[1, 2, 6][3, 4, 5]
[1, 3, 4][2, 5, 6]
[1, 3, 5][2, 4, 6]
[1, 3, 6][2, 4, 5]
[1, 4, 5][2, 3, 6]
[1, 4, 6][2, 3, 5]
[1, 5, 6][2, 3, 4]
于 2013-03-27T13:25:24.997 に答える
1

組み合わせて考えてください。の場合、要素n % k != 0が少ない1つのセットになってしまうため、それを行うことはできません。そのため、それが当てはまるかどうかを確認することから始めます。k

その後、あなたがする必要があるのは、n-i*kすべてのセットからk-combinationsを再帰的に生成することi in [0; n/k]です。与えられたセットのすべてのkの組み合わせを生成するためのアルゴリズムは、非常に簡単に見つけることができます。アイデアは次のとおりです。最初のセットに選択できるそのようなセットは（n個選択k）あります。残りのn-k要素から、（（nk）choose k）セットを選択できます）; 残りのn-2k要素から、（（n-2k）選択k）セットなどを選択できます。セットの順序が重要ではないと仮定すると、セット(n choose k) * ((n-k) choose k) * ... * ((n-(n-1)k) choose k) / ((n/k)!)を選択する可能性があります。これは、kに応じて、元のセットが持つ要素の数で指数関数的になる可能性があるため、本当にすべてのセットを作成する場合は、指数関数的な複雑さを下回ることはありません。

于 2013-03-27T13:51:10.913 に答える
0

誰かが面白いと思った場合に備えて、可能なサブグループの数の式を見つけました。（これはあまりにもトピックから外れていると見なされますか？これを正しく投稿していますか？）
まずm = n/k、サブグループの数とします。ここで、最初のサブグループをグループの最初のk個の要素として固定し、2番目のサブグループを次のk個として固定します。グループのすべての可能な順列を考慮すると、これにより、すべての異なるサブグループが得られます。n個の要素にはn!順列がありますが、順序は気にしないためk!、m個のサブグループのそれぞれのm!順列とサブグループ自体の順列を除外します。これにより、次のことが可能になります n!/(m!*(k!)^m)。
チェックとして、k=1またはk=nの場合、これにより1つのサブグループが作成されます。元の例では、n = 6、k = 3、m = 2であり、10個の可能なサブグループを取得します（Heusterのコードで見つかりました）。
ここで、この式をG. Bachが与えて使用した式と比較すると(n choose k) = n!/(k!*(n-k)!)、すべての(n-k)!用語がキャンセルされ、上記の式に還元されることがわかります。
ボーナス：スターリングの近似をに使用するとn!、式はうまく単純化され、サブグループの数はとしてスケーリングされ(m^n)/m!ます。

于 2013-03-28T03:32:35.740 に答える