私は次のような問題を解決するために探している数字

Question

のセットのために特定の大きさのすべての可能な組み合わせを探します... n。

組み合わせがソートされていることを確認してください。要素をソートする必要があり、すべてのエントリの中で、

1. を詳しく説明し

   。 [1,4]は有効なエントリであり、[4,1]は有効ではありません。

2. エントリは、それ自身でソートする必要があります。

例： 場合、N = 2 = 4、kは、溶液である：

[
      [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 *（NK）！！）

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]