我正在寻求解决以下问题:
给定两个整数 n 和 k,返回 1 2 3 ... n 中 k 个数字的所有可能组合。
确保组合已排序。
详细说明,
- 在每个条目中,元素都应该排序。 [1, 4] 是有效条目,而 [4, 1] 则无效。
- 条目应在其内部排序。
示例: 如果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)!)
最佳答案
您可以直接按正确的顺序生成它们(伪代码):
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]
关于java - 查找一组数字的特定大小的所有可能组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39318920/