如何将整数数组分成所有可能的N部分组合？

Question

我正在尝试将一个数组分成N个部分，条件是每个部分都至少包含一个数字。

例如：如果将数组 [5, 10, 10, 30] 分为2（N=2）个部分，则所有可能的部分组合如下：

• 组合 #1：5 | 10, 10, 30
• 组合 #2：5, 10 | 10, 30
• 组合 #3：5, 10, 10 | 30

我的代码如下：

public static void main(String[] args) {

        int[] a = { 5, 10, 10, 30 };
        int maxElement = 3;
        int count = 1;
        while (count <= maxElement) {
            printCombinations(count, a);
            count++;
        }

    }

    public static void printCombinations(int count, int[] a) {
        System.out.println("start printing");
        for (int index = 0; index < count; index++) {

            System.out.println(a[index]);
        }
        System.out.println("----");
        for (int index = count; index < a.length; index++) {

            System.out.println(a[index]);
        }
        System.out.println("end printing");
    }

它按预期打印组合。但我无法弄清如何将其推广到N。任何帮助都将不胜感激。

- fellow_dev

---

部分总是按顺序排列的吗？例如，对于N=2，“5,30 | 10,10”不是有效的第4个解决方案吗？ - Max Vollmer

@TheScientificMethod：5 | 10 | 10,30; 5,10 | 10 | 30; 和 5 | 10,10 | 30。 - InconsistentHashing

啊，没事了，我明白了……这些是“选项”，而不是结果。 - dognose

技术术语是分区，例如对于大小为 5 的数组当 N=3 时，这意味着我们要用恰好3个加数将 5 进行分区。 - The Scientific Method

在math.stackexchange上有一个类似的问题：将n写成k个非负整数之和的方式数量。在您的情况下，n是数组长度，k是分区数。 - teppic

Answer 1

我必须将数组转换为ArrayList，以便更轻松地处理数据集。

我使用递归来分离数组的左侧部分并递归计算右侧部分。

可能不是最好的代码，但它可以工作。如果有时间，我会尝试改善变量名称。

解释List<List<List<Integer>>>的用法：-

假设输入是

a = { 5, 10, 10, 30 }
n = 2

组合将是：

combination #1: 5 | 10, 10, 30
combination #2: 5, 10 | 10, 30
combination #3: 5, 10, 10 | 30

为了存储这3个组合，使用最外层的List<>。

第二个List<>存储每个组合中的部分。因此，组合#1将有2个部分，[5]和[10, 10, 30]。

最内层的List<Integer>用于存储每个部分中的整数。因此，组合#1中的第2个部分将有一个包含10、10、30的列表。

解决方案

public static void main(String[] args) {
    Integer[] a = {5, 10, 10, 30};
    final List<List<List<Integer>>> combinations = getCombinations(2, Arrays.asList(a));
    for (List<List<Integer>> combination : combinations)
        System.out.println(combination);
}

public static List<List<List<Integer>>> getCombinations(int n, List<Integer> a) {
    if (n == 1) {
        List<List<List<Integer>>> singleLine = new ArrayList<>();
        List<List<Integer>> singleSection = new ArrayList<>();
        singleSection.add(a);
        singleLine.add(singleSection);
        return singleLine;
    }
    List<List<List<Integer>>> res = new ArrayList<>();
    if (n > a.size()) return res;
    if (n == a.size()) {
        List<List<Integer>> sections = new ArrayList<>();
        for (Integer e : a) {
            List<Integer> l = new ArrayList<>();
            l.add(e);
            sections.add(l);
        }
        List<List<List<Integer>>> lines = new ArrayList<>();
        lines.add(sections);
        return lines;
    }
    for (int i = 1; i <= a.size() - n + 1; i++) {
        List<List<Integer>> left = new ArrayList<>();
        List<Integer> leftElements = new ArrayList<>();
        left.add(leftElements);
        leftElements.addAll(a.subList(0, i));
        List<List<List<Integer>>> subResult = getCombinations(n - 1, a.subList(i, a.size()));
        for (List<List<Integer>> r : subResult) {
            res.add(Stream.concat(left.stream(), r.stream())
                    .collect(Collectors.toList()));
        }
    }
    return res;
}

输入 1

a = {5, 10, 10, 30}
n = 2

输出 1

[[5], [10, 10, 30]]
[[5, 10], [10, 30]]
[[5, 10, 10], [30]]

输入 2

a = {5, 10, 10, 30}
n = 3

输出 2

[[5], [10], [10, 30]]
[[5], [10, 10], [30]]
[[5, 10], [10], [30]]

输入 3

a = {5, 10, 10, 30, 40}
n = 3

输出 3

[[5], [10], [10, 30, 40]]
[[5], [10, 10], [30, 40]]
[[5], [10, 10, 30], [40]]
[[5, 10], [10], [30, 40]]
[[5, 10], [10, 30], [40]]
[[5, 10, 10], [30], [40]]

- Kartik