从数组中获得大小为n的所有组合的算法(Java)？
从数组中获得大小为n的所有组合的算法(Java)？
提问于 2015-04-28 12:25:03
现在，我正在尝试编写一个函数，该函数接受一个数组和一个整数n，并给出每个大小为n的组合的列表(因此是一个整数数组列表)。我可以使用n个嵌套循环来编写它，但这只适用于特定大小的子集。我不知道如何将其推广到任何大小的组合中。我想我需要使用递归？
这是3个元素的所有组合的代码，我需要一个任意数量的元素的算法。
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("\n");
}
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2015-04-28 17:02:27
这是一个研究得很好的生成所有k-子集或k-combinations的问题，可以很容易地完成，而不需要递归。
其思想是让大小为k的数组保持输入数组中元素的索引顺序(从0到n - 1的数字)按升序排列。(然后可以通过从初始数组中按这些索引获取项来创建子集。)所以我们需要生成所有这样的索引序列。
第一个索引序列将是[0, 1, 2, ... , k - 1]，第二步将切换到[0, 1, 2,..., k]，然后切换到[0, 1, 2, ... k + 1]，依此类推。最后一个可能的序列是[n - k, n - k + 1, ..., n - 1]。
在每一步中，算法都会查找最接近可以递增的成品，对其进行递增，并将条目填充到该条目的右侧。
为了说明这一点，我们以n = 7和k = 3为例。第一个索引序列是[0, 1, 2]，然后是[0, 1, 3]，依此类推...在某种程度上，我们有了[0, 5, 6]
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"因此，[0, 5, 6]之后是[1, 2, 3]，然后是[1, 2, 4]，依此类推。
代码：
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29910312
复制相关文章
相似问题
腾讯云开发者
