从数组（Java）中获取大小为 n 的所有组合的算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29910312/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to get all the combinations of size n from an array (Java)?
提问by Esostack
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?
现在我正在尝试编写一个函数，它接受一个数组和一个整数 n，并给出每个大小 n 组合的列表（因此是一个 int 数组列表）。我可以使用 n 个嵌套循环来编写它，但这仅适用于特定大小的子集。我不知道如何将它概括为适用于任何大小的组合。我想我需要使用递归？
This is the code for all combinations of 3 elements, and I need an algorithm for any number of elements.
这是 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");
}
}
}
采纳答案by Alex Salauyou
This is a well-studied problem of generating all k-subsets, or k-combinations, which can be easily done without recursion.
这是生成所有 k 子集或k 组合的经过充分研究的问题，无需递归即可轻松完成。
The idea is to have array of size kkeeping sequence of indicesof elements from the input array (which are numbers from 0to n - 1) in increasing order. (Subsetthen can be created by taking items by these indices from the initial array.) So we need to generate all such index sequences.
这个想法是让大小数组k保持输入数组中元素的索引序列（它们是从0到 的数字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].
第一个索引序列将是[0, 1, 2, ... , k - 1]，在第二步它切换到[0, 1, 2,..., k]，然后切换到[0, 1, 2, ... k + 1]等等。最后一个可能的序列是[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.
在每一步，算法寻找最接近可以递增的最终项目，递增它并填充该项目的正确项目。
To illustrate, consider n = 7and k = 3. First index sequence is [0, 1, 2], then [0, 1, 3]and so on... At some point we have [0, 5, 6]:
为了说明，考虑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"
Thus, [0, 5, 6]is followed by [1, 2, 3], then goes [1, 2, 4]etc.
因此，[0, 5, 6]后面是[1, 2, 3]，然后是[1, 2, 4]等等。
Code:
代码：
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;
}
回答by Raniz
You can do definitely this with iteration.
你绝对可以通过迭代做到这一点。
Here's one solution that calculates how many arrays we should create and then builds them using math to calculate which item from the source array should be in what place:
这是一种计算我们应该创建多少数组然后使用数学构建它们来计算源数组中的哪个项目应该在什么位置的解决方案：
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
int[] current = new int[n];
// Calculate the correct item for each position in the array
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
list.add(current);
}
}
Update:
更新：
Here's an optimised version that significantly reduces the number of calls to Math.pow
这是一个优化版本，可显着减少调用次数 Math.pow
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
list.add(new int[n]);
}
// Fill up the arrays
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
for(int i = 0; i < numArrays; i++) {
int[] current = list.get(i);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
}
}
回答by Roney Michael
If I understood your problem correctly, thisarticle seems to point to what you're trying to do.
如果我正确理解您的问题，这篇文章似乎指向了您正在尝试做的事情。
To quote from the article:
引用文章：
Method 1 (Fix Elements and Recur)
We create a temporary array ‘data[]' which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].
Method 2 (Include and Exclude every element)
Like the above method, We create a temporary array data[]. The idea here is similar to Subset Sum Problem. We one by one consider every element of input array, and recur for two cases:
- The element is included in current combination (We put the element in data[] and increment next available index in data[])
- The element is excluded in current combination (We do not put the element and do not change index)
When number of elements in data[] become equal to r (size of a combination), we print it.
方法 1（修复元素并重复）
我们创建了一个临时数组 'data[]' 来一一存储所有输出。这个想法是从 data[] 中的第一个索引（索引 = 0）开始，在这个索引处一个一个地修复元素，并重复剩余的索引。让输入数组为 {1, 2, 3, 4, 5} 并且 r 为 3。我们首先在 data[] 中的索引 0 处固定 1，然后对剩余索引进行递归，然后在索引 0 处固定 2 并递归。最后，我们修复 3 并重复剩余索引。当 data[] 中的元素数等于 r（组合的大小）时，我们打印 data[]。
方法 2（包含和排除每个元素）
和上面的方法一样，我们创建了一个临时数组data[]。这里的想法类似于子集和问题。我们将输入数组的每一个元素都一一考虑，并重复出现两种情况：
- 该元素包含在当前组合中（我们将元素放在 data[] 中并增加 data[] 中的下一个可用索引）
- 元素被排除在当前组合中（我们不放元素，不改变索引）
当 data[] 中的元素数等于 r（组合的大小）时，我们打印它。
