所有可能的大小为n的列表的k组合

huangapple go评论74阅读模式
英文:

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&lt;Human&gt; people, int k, ArrayList&lt;List&gt; result) {
    if (people.size() &lt; k) {
        return;
    }
    if (k == 1) {
        for (Human hum : people) {
            List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
            combinations.add(hum);
            result.add(combinations);
        }
    }
    else if (people.size() == k) {
        List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
        for (Human hum : people) {
            combinations.add(hum);
        }
       result.add(combinations);
    }
    else if (people.size() &gt; k) {
        for (int i = 0; i &lt; people.size(); i++) {
            List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
            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&lt;Human&gt; people, int k, ArrayList&lt;List&gt; result) {
    if (people.size() &lt; k) {
        return;
    }
    if (k == 1) {
        for (Human hum : people) {
            List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
            combinations.add(hum);
            result.add(combinations);
        }
    }
    else if (people.size() == k) {
        List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
        for (Human hum : people) {
            combinations.add(hum);
        }
       result.add(combinations);
    }
    else if (people.size() &gt; k) {
        for (int i = 0; i &lt; people.size(); i++) {
            List&lt;Human&gt; combinations = new ArrayList&lt;Human&gt;();
            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&lt;Human&gt; humans, int k, int index, Set&lt;Human&gt; tempSet, List&lt;Set&lt;Human&gt;&gt; finalSet) {
    if (tempSet.size() == k) {
        finalSet.add(new HashSet&lt;&gt;(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&lt;Set&lt;Human&gt;&gt; combination(List&lt;Human&gt; humans, int k) {
    List&lt;Set&lt;Human&gt;&gt; result = new ArrayList&lt;&gt;();
    subsetsOf(humans, k, 0, new HashSet&lt;Human&gt;(), 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 &lt;T&gt;             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 &lt;T&gt; List&lt;List&lt;T&gt;&gt; createCombinations(List&lt;T&gt; elts, int combinationSize) {
var fullCombinations = new ArrayList&lt;List&lt;T&gt;&gt;();
createCombinations(elts, fullCombinations, new ArrayList&lt;T&gt;(), 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 &lt;code&gt;missing == 0&lt;/code&gt;.
* 
* @param &lt;T&gt;              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 &lt;code&gt;missing&lt;code&gt; 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 &lt;T&gt; void createCombinations(List&lt;T&gt; elts, List&lt;List&lt;T&gt;&gt; fullCombinations, List&lt;T&gt; combination,
int index, int missing) {
if (missing == 0) {
fullCombinations.add(combination);
return;
}
// we don&#39;t need to go over elts.size() - missing because then the combination cannot be completed, too few left
for (int i = index; i &lt;= elts.size() - missing; i++) {
List&lt;T&gt; newCombination;
if (i == elts.size() - missing) {
// optimization: avoid dereferencing the final combination, reuse
newCombination = combination;
} else {
newCombination = new ArrayList&lt;T&gt;(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&lt;Human&gt;();
for (int id = 0; id &lt; 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&lt;Human&gt; 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.

huangapple
  • 本文由 发表于 2020年4月4日 22:45:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/61029823.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定