3

我遇到了一个问题：找到将一组大小为 '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，你不能这样做，因为你最终会得到一组少于k元素的集合，所以从检查是否是这种情况开始。

之后，您需要做的就是从一个n-i*k集合中递归地为 all生成 k 组合i in [0; n/k]。可以很容易地找到生成给定集合的所有 k 组合的算法。这个想法是：有（n个选择k）可能的这样的集合，你可以为你的第一个集合选择；从剩下的n-k元素中，你可以选择（（nk）选择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 个元素，第二个子群是下一个 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 回答