从数组中获取大小为n的所有组合的算法(Java)? [英] Algorithm to get all the combinations of size n from an array (Java)?
问题描述
现在我正在尝试编写一个接受数组和整数n的函数,并给出每个大小为n的组合的列表(所以是int数组的列表)。我能够使用n个嵌套循环编写它,但这仅适用于特定大小的子集。我无法弄清楚如何推广它适用于任何大小的组合。我想我需要使用递归?
Right now I'm trying to write a function that takes an array and an integer n, and gives a list of each size n combination (so a list of int arrays). I am able to write it using n nested loops, but this only works for a specific size of subset. I can't figure out how to generalize it to work for any size of combination. I think I need to use recursion?
这是3个元素的所有组合的代码,我需要一个适用于任意数量元素的算法。
This is the code for all combinations of 3 elements, and I need an algorithm for any number of elements.
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");
}
}
}
推荐答案
这是一个生成所有k子集的充分研究的问题,或 k-combinations ,这可以在没有递归的情况下轻松完成。
This is a well-studied problem of generating all k-subsets, or k-combinations, which can be easily done without recursion.
我们的想法是让数组大小 k
保持序列输入数组中元素的 indices (从 0
到 n - 1
的数字)按顺序递增。 ( Subset 然后可以通过从初始数组中通过这些索引获取项目来创建。)因此我们需要生成所有这样的索引序列。
The idea is to have array of size k
keeping sequence of indices of elements from the input array (which are numbers from 0
to n - 1
) in increasing order. (Subset then can be created by taking items by these indices from the initial array.) So we need to generate all such index sequences.
第一个索引序列将是 [0,1,2,...,k - 1]
,第二步它切换到 [0, 1,2,...,k]
,然后到 [0,1,2,... k + 1]
等等。最后一个可能的序列是 [n - k,n - k + 1,...,n - 1]
。
First index sequence will be [0, 1, 2, ... , k - 1]
, on the second step it switches to [0, 1, 2,..., k]
, then to [0, 1, 2, ... k + 1]
and so on. The last possible sequence will be [n - k, n - k + 1, ..., n - 1]
.
在每一步中,算法会查找最接近最终项目的值,该项目可以递增,递增并将项目填充到该项目。
On each step, algorithm looks for the closest to the end item which can be incremented, increments it and fills up items right to that item.
为了说明,请考虑 n = 7
和 k = 3
。第一个索引序列是 [0,1,2]
,然后是 [0,1,3]
等等。 ..在某些时候我们有 [0,5,6]
:
To illustrate, consider n = 7
and k = 3
. First index sequence is [0, 1, 2]
, then [0, 1, 3]
and so on... At some point we have [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]
等等。
Thus, [0, 5, 6]
is followed by [1, 2, 3]
, then goes [1, 2, 4]
etc.
代码:
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;
}
这篇关于从数组中获取大小为n的所有组合的算法(Java)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!