将一个群组分成大小为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的组合。 然后循环这些组合，找出哪些组合可以组合在一起，以此来找出子组的列表。

但是我认为这种方法的时间复杂度相当糟糕。有没有更好的方法解决这个问题呢？

- vishnu viswanath

---

{1,2,3},{4,5,6}和{4,5,6},{1,2,3} - 你认为它们是相同的分割还是不同的？ - MBo

请展示您的代码。您的描述对我来说没有意义。 - Stephen C

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]

- Vincent van der Weele

---

你可以在 ArrayList 的构造函数中指定容量，以避免昂贵的扩展操作。 - G. Bach

@G.Bach 很聪明！我会加上的。 - Vincent van der Weele

Answer 2

考虑组合方式。如果 n % k != 0，则无法进行操作，因为最终会得到一个少于 k 个元素的集合，因此首先检查是否存在这种情况。

之后，您只需要对所有 i [0; n/k] 的 n-i*k 集合递归地生成 k-组合即可。可以在 SO 上找到用于生成给定集合的所有 k-组合的算法。思路是：有 (n choose k) 种可能的这样的集合可以选择作为第一个集合；从剩余的 n-k 元素中，您可以选择 ((n-k) choose k) 个集合）；从剩余的 n-2k 元素中，您可以选择 ((n-2k) choose k) 个集合，依此类推。假设您的集合顺序不重要，则您有 (n choose k) * ((n-k) choose k) * ... * ((n-(n-1)k) choose k) / ((n/k)!) 种选择集合的可能性，具体取决于 k，可能会呈指数级增长，因此如果您真的想要生成每个集合，您将无法避免指数复杂度。

- G. Bach

Answer 3

我找到了一种计算可能子群数量的公式，如果有人觉得有趣的话。（这是否被认为太离题了？我是否正确地发布了这个问题？）
首先让 m = n/k 成为子群的数量。现在让第一个子群固定为组的前k个元素，第二个子群为接下来的k个元素，以此类推。如果我们考虑组的所有可能排列，这将给我们所有不同的子群。有 n! 个n个元素的排列，但我们不关心顺序，所以我们将每个m个子群和子群本身的 k! 排列和 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! 的比例增长。

- napolj2

---

在你的公式中，为什么要使用^m？抱歉，我不擅长数学。 - vishnu viswanath

没问题。^m 是因为有 m 个不同的子组。每个子组都有 k! 种不同的元素排列方式，所以你需要为每个子组除以 k!。因此，在您最初的示例中，n = 6，k = 3，元素的总排列数为 6！，但我们要除以 3!，因为第一个子组内的元素顺序无关紧要，再除以 3!，然后再除以 2!，因为子组本身的顺序不重要。这给了我们 10。 - napolj2