将一个整数分成若干"groups"的所有组合

Question

假设我=有 5 块糖果，我想找到所有可能的组合，让我的 3 个孩子分享它们。

这将类似于下面的内容：

5 for kid_A, 0 for kid_B, 0 for kid_3
0 for kid_A, 5 for kid_B, 0 for kid_3
....
4 for kid_A, 1 for kid_B, 0 for kid_3
4 for kid_A, 0 for kid_B, 1 for kid_3
....
and so on

是否有算法可以找到这些组合？

到目前为止，我已经设法计算出前 3 个组合，我把所有的糖果都给了我的一个孩子，剩下的得到 0；但是一旦我完成了第一次迭代，我就不知道如何划分了。

Answer 1

这个问题分为三个方面：

我可以给一个 child 最多 N 种糖果多少种方式？（每个 child 的排列）
对于其中的每一个，我有多少种方法可以给另一个 child 剩下的 N 颗糖果？（可能是递归）
我什么时候停止分糖果？（终止）

有多少种方法可以给出 child n 个糖果很简单：每个 0 -> n 都有一个排列，例如第一个child可以给0、1、2、3、4或5个糖果。

对于第二个 child，您可以在减去第一个 child 的糖果数量后重复此操作。因此，对于 0 -> m，其中 m = 5 - n.

对于 n 和 m 的每一个排列，第三个 child 简单地得到余数：t = 5 - (n + m)。

据此，您可以制定两个循环来生成您的排列。对于任何数量的 children 或 sweets 都有更一般的情况，但是你必须小心你的递归（堆栈大小问题）并意识到对于大量的组合可能是巨大的。

Answer 2

代码

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Example {
    public static void main(final String... args) {
        for (final List<Integer> option : divide(5, 3)) {
            System.out.printf("%d for kid_A, %d for kid_B, %d for kid_3%n", option.toArray());
        }
    }

    private static List<List<Integer>> divide(final int count, final int groups) {
        if (groups == 1) {
            final List<Integer> inner = new ArrayList<>(1);
            inner.add(count);
            final List<List<Integer>> outer = new ArrayList<>(1);
            outer.add(inner);
            return outer;
        }
        return IntStream.range(0, count + 1)
            .mapToObj(Integer::valueOf)
            .flatMap(p -> {
                return divide(count - p, groups - 1).stream()
                    .map(q -> {
                        q.add(p);
                        return q;
                    });
            }).collect(Collectors.toList());
    }
}

工作原理

这从基本假设开始，即如果您有 1 个孩子，您会把所有的糖果都给他们。

如果您有多个孩子，它会计算给第一个孩子多少个，然后递归找出其他孩子可以有多少个。

flatMap获取所有选项，加上当前child获取的糖果数量

将一个整数分成若干"groups"的所有组合

All combinations of dividing an integer into several "groups"

java

algorithm

computation

代码

工作原理