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

java combinations combinatorics

2022-09-01 08:14:56

现在，我正在尝试编写一个函数，该函数采用数组和整数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");
        }
    }
}

答案 1

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

这个想法是让大小数组保持输入数组（从到的数字）的元素索引序列按递增的顺序排列。（然后，可以通过从初始数组中按这些索引获取项目来创建子集。因此，我们需要生成所有此类索引序列。k0n - 1

第一个索引序列将是，在第二步中它切换到，然后切换到 to 等等。最后一个可能的序列将是。[0, 1, 2, ... , k - 1][0, 1, 2,..., k][0, 1, 2, ... k + 1][n - k, n - k + 1, ..., n - 1]

在每个步骤中，算法都会查找最接近成品的成品，该成品可以递增，递增它并填充该项目。

为了说明这一点，请考虑和。第一个索引序列是，然后依此类推...在某些时候，我们有：n = 7k = 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;
}

答案 2

如果我正确地理解了您的问题，那么本文似乎指向了您要执行的操作。

引用文章：

方法 1（修复元素和重复）

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

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

像上面的方法一样，我们创建一个临时数组数据[]。这里的想法类似于子集总和问题。我们逐一考虑输入数组的每个元素，并在两种情况下重复：

该元素包含在当前组合中（我们将元素放在data[]中，并在data[]中增加下一个可用索引）

该元素在当前组合中被排除（我们不放置元素，也不更改索引）

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