java - 如何以所有可能的组合将整数数组分解为 N 部分?
问题描述
我试图将一个数组分成 N 个部分,条件是所有部分都至少有 1 个数字。
示例:如果数组 [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 概括这一点。感谢任何帮助。
解决方案
我必须将数组转换为 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>
用于存储每个部分内的整数。因此,第 2 节结合第 1 节将有一个 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]]
推荐阅读
- c - 声明与“__interwork __vfp”不兼容
- reactjs - 为什么将 Electron 与 SPA 框架一起使用?
- linux - 如何在linux中将文件的每一列除以单独文件中的一行?
- three.js - 三.js obj/mtl模型突然显示黑色
- python - 在 Anaconda Python 中安装 Keras 和 TensorFlow 时遇到问题
- apache-spark - 检查 YARN 集群上是否启用了 External Shuffle Service
- python - 在谷歌云功能中使用 PubSub
- javascript - 更改路线时不执行 Framer Motion AnimatePresence
- java - 为什么 Java 和 C 中按位左移的结果不同?
- python - django模板上的关注/取消关注按钮