将一组划分为大小为k的子组

Question

我遇到了一个问题:找到将一组大小'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的所有组合.然后循环遍历这些组合,找出哪些组合可以组合在一起以找到子组列表.

但我相信这种方法的时间复杂性非常糟糕.有没有更好的方法来解决这个问题？

Answer 1

我会使用递归方法.我认为这个有最佳的运行时间,因为它确切地产生了所有需要的子集.

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]