从数组中获取大小为n的所有组合的算法（Java）？
现在我正在尝试编写一个带有数组和整数n的函数，并给出每个大小为n的组合的列表（所以是int数组的列表）。 我能够使用n个嵌套循环编写它，但这仅适用于特定大小的子集。 我无法弄清楚如何推广它适用于任何大小的组合。 我想我需要使用递归？
这是3个元素的所有组合的代码，我需要一个适用于任意数量元素的算法。
import java.util.List; import java.util.ArrayList; public class combinatorics{ public static void main(String[] args) { List list = new ArrayList(); int[] arr = {1,2,3,4,5}; combinations3(arr,list); listToString(list); } static void combinations3(int[] arr, List 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 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组合的充分研究的问题，其可以在没有递归的情况下容易地完成。
这个想法是使大小为k数组保持输入数组的元素索引序列（从0到n - 1 ）按递增顺序排列。 （然后可以通过从初始数组中通过这些索引获取项来创建子集 。）因此我们需要生成所有这样的索引序列。
第一个索引序列为[0, 1, 2, ... , k - 1] ，第二个步骤切换为[0, 1, 2,..., k] ，然后切换为[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 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; }
如果我正确地理解了你的问题，那么这篇文章似乎指出了你想要做的事情。
引用文章：
方法1（修复元素和重复）
我们创建一个临时数组’data []’，它逐个存储所有输出。 我们的想法是从data []中的第一个索引（index = 0）开始，在此索引处逐个修复元素，并为剩余索引重复。 让输入数组为{1,2,3,4,5}，r为3.我们首先在data []中的索引0处修复1，然后对剩余的索引重复，然后在索引0处修复2并重复。 最后，我们修复3并重复剩余的索引。 当data []中的元素数量等于r（组合的大小）时，我们打印数据[]。
方法2（包含和排除每个元素）
像上面的方法一样，我们创建一个临时数组数据[]。 这里的想法类似于子集和问题。 我们逐个考虑输入数组的每个元素，并重复两种情况：
- 元素包含在当前组合中（我们将元素放在data []中并递增data []中的下一个可用索引）
- 当前组合中排除了该元素（我们不放置元素而不更改索引）
当data []中的元素数量等于r（组合的大小）时，我们将其打印出来。
你可以通过迭代来做到这一点。
这是一个解决方案，它计算我们应该创建多少个数组，然后使用math来构建它们来计算源数组中的哪个项应该在哪个位置：
public static void combinations(int n, int[] arr, List 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, ie // 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); } }
更新：
这是一个优化版本，可显着减少对Math.pow的调用次数
public static void combinations(int n, int[] arr, List 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, ie // 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]; } } }