从数组中获取大小n的所有组合的算法（Java）？[关闭]

Question

编辑问题以包含所需的行为、特定问题或错误以及重现问题所需的最短代码。这将帮助其他人回答问题。

现在我正在尝试编写一个函数，它接受一个数组和一个整数n，并给出每个大小n组合的列表（因此是一个int数组列表）。我可以使用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");
        }
    }
}

Answer 1

你可以通过迭代来做到这一点。

这是一种计算我们应该创建多少个数组的解决方案，然后使用数学构建它们来计算源数组中的哪个项目应该在什么位置：

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);
    }
}

更新：

这是一个优化版本，可以显著减少调用数学的次数。功率

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];
        }
    }
}

Answer 2

如果我正确理解了你的问题，这篇文章似乎指出了你想做什么。

引用文章：

方法1（固定元素并重复）

我们创建一个临时数组“data[]”，它逐个存储所有输出。其思想是从数据[]中的第一个索引（索引=0）开始，在此索引处逐个固定元素，并重复出现其余索引。设输入数组为{1，2，3，4，5}，r为3。我们首先在数据[]中的索引0处固定1，然后对其余索引重复，然后在索引0处固定2并重复。最后，我们修复了3，并对其余索引进行了递归。当数据[]中的元素数等于r（组合大小）时，我们打印数据[]。

方法2（包括和排除每个元素）

与上述方法类似，我们创建了一个临时数组数据[]。这里的思想类似于子集和问题。我们逐个考虑输入数组的每个元素，并重复出现两种情况：

1. 该元素包含在当前组合中（我们将该元素放入数据[]，并在数据[]中增加下一个可用索引）
2. 元素在当前组合中被排除（我们不放置元素，也不更改索引）

当数据[]中的元素数等于r（组合大小）时，我们打印它。

Answer 3

这是一个经过充分研究的生成所有k子集或k组合的问题，无需递归即可轻松完成。

其思想是使大小为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;
}