英文:
All Possible k combinations of list with size n
问题
我正在尝试从大小为 N 的列表中获取大小为 K 的所有可能组合。
我有一个接受“Human”对象的列表,并且我试图创建一个新的ArrayList,其中将填充List<Human>对象。每个列表都将是不同的“Human”对象组合。
一个简单的数字示例是:从包含 1、2、3 的列表中,我想要获得一个ArrayList,它看起来像这样:[[1,2], [1,3], [2,3]]
我也不介意它看起来像这样:[[1], [2], [3], [1,2], [1,3], [2,3]]
以下是我的代码:
public void combination(List<Human> people, int k, ArrayList<List> result) {
if (people.size() < k) {
return;
}
if (k == 1) {
for (Human hum : people) {
List<Human> combinations = new ArrayList<Human>();
combinations.add(hum);
result.add(combinations);
}
}
else if (people.size() == k) {
List<Human> combinations = new ArrayList<Human>();
for (Human hum : people) {
combinations.add(hum);
}
result.add(combinations);
}
else if (people.size() > k) {
for (int i = 0; i < people.size(); i++) {
List<Human> combinations = new ArrayList<Human>();
combinations.add(people.get(i));
result.add(combinations);
combination(people.subList(i + 1, people.size()), k - 1, result);
}
}
}
我正在使用此网站上的最后一个方法作为参考:https://hmkcode.com/calculate-find-all-possible-combinations-of-an-array-using-java/
目前,我在新的ArrayList中得到了正确数量的结果,但每个列表内部只包含单个Human。
我非常怀疑问题在于最后的 else if
部分,因为我很难理解递归。
请随意提问或建议其他实现方式。
英文:
I am trying to get all possible combinations of size K from a list of size N.
I have a List that takes "Human" objects and I am trying to create a new ArrayList which will be filled with List<Human> objects. Each of the Lists will be a different combination of "Human" objects.
A simple example with numbers would be: From a list consisting 1,2,3 I want to get an ArrayList which looks like this: [[1,2], [1,3], [2,3]]
I also wouldn't mind if it looks like this: [[1], [2], [3], [1,2], [1,3], [2,3]]
Here is my code:
public void combination(List<Human> people, int k, ArrayList<List> result) {
if (people.size() < k) {
return;
}
if (k == 1) {
for (Human hum : people) {
List<Human> combinations = new ArrayList<Human>();
combinations.add(hum);
result.add(combinations);
}
}
else if (people.size() == k) {
List<Human> combinations = new ArrayList<Human>();
for (Human hum : people) {
combinations.add(hum);
}
result.add(combinations);
}
else if (people.size() > k) {
for (int i = 0; i < people.size(); i++) {
List<Human> combinations = new ArrayList<Human>();
combinations.add(people.get(i));
result.add(combinations);
combination(people.subList(i + 1, people.size()), k - 1, result);
}
}
}
I am using the last method in this site as a reference: https://hmkcode.com/calculate-find-all-possible-combinations-of-an-array-using-java/
At the moment I get the correct number of results in my new ArrayList but each List inside only consist of a single Human.
I highly suspect the problem lies in the last else if
because I have hard time understanding the recursion.
Please feel free to ask any questions or suggest any other implementation for this.
答案1
得分: 2
问题出在你的循环中,你只在连续的子列表上调用了 combination
函数(例如,如果初始集合是 [1,2,3,4,5],你没有在 [1,3,5] 这样的子列表上调用该函数)。
此外,请记得在你的 Human
类中重写 equals
函数。
private void subsetsOf(List<Human> humans, int k, int index, Set<Human> tempSet, List<Set<Human>> finalSet) {
if (tempSet.size() == k) {
finalSet.add(new HashSet<>(tempSet));
return;
}
if (index == humans.size())
return;
Human human = humans.get(index);
tempSet.add(human);
subsetsOf(humans, k, index+1, tempSet, finalSet);
tempSet.remove(human);
subsetsOf(humans, k, index+1, tempSet, finalSet);
}
public List<Set<Human>> combination(List<Human> humans, int k) {
List<Set<Human>> result = new ArrayList<>();
subsetsOf(humans, k, 0, new HashSet<Human>(), result);
return result;
}
英文:
The problem is in your loop, you are calling combination
function only on continuous sublists (for instance if the initial set is [1,2,3,4,5], you are not calling the function on sublist of [1,3,5]).
Also, keep in mind you should override the equals
function in your Human
class.
private void subsetsOf(List<Human> humans, int k, int index, Set<Human> tempSet, List<Set<Human>> finalSet) {
if (tempSet.size() == k) {
finalSet.add(new HashSet<>(tempSet));
return;
}
if (index == humans.size())
return;
Human human = humans.get(index);
tempSet.add(human);
subsetsOf(humans, k, index+1, tempSet, finalSet);
tempSet.remove(human);
subsetsOf(humans, k, index+1, tempSet, finalSet);
}
public List<Set<Human>> combination(List<Human> humans, int k) {
List<Set<Human>> result = new ArrayList<>();
subsetsOf(humans, k, 0, new HashSet<Human>(), result);
return result;
}
答案2
得分: 0
以下是翻译好的代码部分:
package com.stackexchange.so;
import java.util.ArrayList;
import java.util.List;
public class RecursiveCombinationCreator {
/**
* 创建特定组合大小的元素组合。
*
* @param <T> 元素的类型
* @param elts 一个元素列表,应该是唯一的
* @param combinationSize 组合的大小
* @return 组合的列表
*/
public static <T> List<List<T>> createCombinations(List<T> elts, int combinationSize) {
var fullCombinations = new ArrayList<List<T>>();
createCombinations(elts, fullCombinations, new ArrayList<T>(), 0, combinationSize);
return fullCombinations;
}
/**
* 递归函数,增加组合大小,并在达到组合大小时添加完整的组合。
* 为避免重复,仅添加在列表中较高的元素到组合中。当 missing == 0 时,组合完成。
*
* @param <T> 元素的类型
* @param elts 要从中创建组合的元素,所有元素都应是唯一的
* @param fullCombinations 组合的最终结果数组,在所有递归调用之间共享
* @param combination 当前需要添加 missing 成员的当前组合
* @param index 元素的索引,比组合中最后一个元素高一个位置
* @param missing 完成组合所需的元素数量
*/
private static <T> void createCombinations(List<T> elts, List<List<T>> fullCombinations, List<T> combination,
int index, int missing) {
if (missing == 0) {
fullCombinations.add(combination);
return;
}
// 我们不需要遍历 elts.size() - missing,因为这样组合无法完成,剩余太少了
for (int i = index; i <= elts.size() - missing; i++) {
List<T> newCombination;
if (i == elts.size() - missing) {
// 优化:避免对最终组合进行解引用,重用
newCombination = combination;
} else {
newCombination = new ArrayList<T>(combination);
}
newCombination.add(elts.get(i));
createCombinations(elts, fullCombinations, newCombination, i + 1, missing - 1);
}
}
// === 测试代码 ===
// 我们需要人类,好吧
private static class Human {
private int id;
public Human(int id) {
this.id = id;
}
@Override
public String toString() {
return Integer.toString(id);
}
}
public static void main(String[] args) {
// 生成输入
var humans = new ArrayList<Human>();
for (int id = 0; id < 200; id++) {
var human = new Human(id);
humans.add(human);
}
// 仅此一个调用
var fullcombinations = createCombinations(humans, 199);
// 显示输出
System.out.println(fullcombinations.size());
for (List<Human> combination : fullcombinations) {
System.out.println(combination);
}
}
}
请注意,最大深度等于 k
(或 k + 1
),这意味着您的堆栈不会受到过多递归调用的影响。
英文:
Here's another implementation that never removes anything nor creates spurious lists of anything. It only ever adds when it needs to, no equals
necessary for T
, as long as they are unique by themselves.
Just for the learning experience, right out of the top of my head:
package com.stackexchange.so;
import java.util.ArrayList;
import java.util.List;
public class RecursiveCombinationCreator {
/**
* Creates combinations of elements of a specific combination size.
*
* @param <T> the type of the elements
* @param elts a list of elements, which should be unique
* @param combinationSize the size of the combinations
* @return a list of combinations
*/
public static <T> List<List<T>> createCombinations(List<T> elts, int combinationSize) {
var fullCombinations = new ArrayList<List<T>>();
createCombinations(elts, fullCombinations, new ArrayList<T>(), 0, combinationSize);
return fullCombinations;
}
/**
* Recursive function that grows the combination size, and adds full combinations when the combination size is met.
* To avoid duplicates, only elements that are higher in the list are added to the combination. The combination is
* complete when <code>missing == 0</code>.
*
* @param <T> the type of the elements
* @param elts the elements to create combinations from, all elements should be unique
* @param fullCombinations the final result array of the combinations, shared among all recursive calls
* @param combination the current combination that needs to get <code>missing<code> members
* @param index the index of the element one higher than the last element in the combination
* @param missing the amount of elements needed to complete the combination
*/
private static <T> void createCombinations(List<T> elts, List<List<T>> fullCombinations, List<T> combination,
int index, int missing) {
if (missing == 0) {
fullCombinations.add(combination);
return;
}
// we don't need to go over elts.size() - missing because then the combination cannot be completed, too few left
for (int i = index; i <= elts.size() - missing; i++) {
List<T> newCombination;
if (i == elts.size() - missing) {
// optimization: avoid dereferencing the final combination, reuse
newCombination = combination;
} else {
newCombination = new ArrayList<T>(combination);
}
newCombination.add(elts.get(i));
createCombinations(elts, fullCombinations, newCombination, i + 1, missing - 1);
}
}
// === TEST CODE ===
// we needed humans, OK
private static class Human {
private int id;
public Human(int id) {
this.id = id;
}
@Override
public String toString() {
return Integer.toString(id);
}
}
public static void main(String[] args) {
// generate input
var humans = new ArrayList<Human>();
for (int id = 0; id < 200; id++) {
var human = new Human(id);
humans.add(human);
}
// just that one call
var fullcombinations = createCombinations(humans, 199);
// show output
System.out.println(fullcombinations.size());
for (List<Human> combination : fullcombinations) {
System.out.println(combination);
}
}
}
Note too that the maximum depth is equal to k
(or k + 1
), which means that your stack is safe from too many recursive calls.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论