java - 查找一组数字的特定大小的所有可能组合

Question

我正在寻求解决以下问题:

给定两个整数 n 和 k，返回 1 2 3 ... n 中 k 个数字的所有可能组合。

确保组合已排序。

详细说明，

1. 在每个条目中，元素都应该排序。 [1, 4] 是有效条目，而 [4, 1] 则无效。
2. 条目应在其内部排序。

示例:如果n = 4且k = 2，则解决方案是:

[
   [1,2],
   [1,3],
   [1,4],
   [2,3],
   [2,4],
   [3,4],
]

这是我想出的解决方案:

public ArrayList<ArrayList<Integer>> combine(int n, int k) {

    //variable where the resultant sets of of numbers are to be stored
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    //finding all the subsets from 1-n of size k and storing them in result
    subset(n,result,k);

    //sorting the resultant set of subsets lexicographically
    Collections.sort(result,new Comparator<ArrayList<Integer>>(){

        @Override
        public int compare(ArrayList<Integer> a,ArrayList<Integer> b){

            int aSize = a.size();
            int bSize = b.size();

            for(int i=0;i<(int)Math.min(aSize,bSize);i++){

                int comparison = Integer.compare(a.get(i),b.get(i));
                if(comparison!=0) return comparison;
            }
               return Integer.compare(aSize,bSize);
        }
    });

    return result;
}


void subset(int n,ArrayList<ArrayList<Integer>> result,int size){
    for(int i=0;i<(1<<n);++i){

        //the arraylist to be added to the result
        ArrayList<Integer> element = new ArrayList<Integer>();

        //iterating 2^n times since those are the total number of possible subsets
        for(int j=0;j<n;++j)
            if((i&(1<<j))>0)
                element.add(j+1);


        //only adding the resultant subset to the result if it matches the size criteria
        if(element.size() == size)
            result.add(element);
    }
}

我正在看着这个答案，我忍不住想一定有一种更优化的方法来做到这一点。

从表面上看，该程序的时间复杂度为 O(nlogn * 2^n)。这很糟糕。我正在尝试计算每个子集，然后检查它们是否符合大小标准。有什么方法可以通过仅迭代 nCk 次来找到子集的数量吗？

nCk 是我们希望找到的组合数量。其中 nCk = n!/(k!*(n-k)!)

Answer 1

您可以直接按正确的顺序生成它们(伪代码):

for(i1 =  0 + 1; i1 <= n-k+1; ++i1)
for(i2 = i1 + 1; i2 <= n-k+2; ++i2)
for(i3 = i2 + 1; i3 <= n-k+3; ++i3)
for(i4 = i3 + 1; i4 <= n-k+4; ++i4)
....
for(ik = i? + 1; ik <= n-k+k; ++ik){
    output = [i1, i2, i3, ..., ik];
}

由于您不是即时创建代码，因此您可以通过递归来实现，如下所示:

private static void Iterate(int[] outp, int n, int k, int actIndex, int lastVal)
{
    if (actIndex > k)
    {
        System.out.println(Arrays.toString(outp));
        return;
    }

    for (int i = lastVal + 1; i <= n - k + actIndex; ++i)
    {
        outp[actIndex - 1] = i;
        Iterate(outp, n, k, actIndex + 1, i);
    }
}

并调用它:

int n = 4;
int k = 2;
Iterate(new int[k], n, k, 1, 0);

输出:

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]