나는 다음과 같은 문제를 해결하기 위해 찾고 있어요 숫자

Question

세트의 특정 크기의 모든 가능한 조합을 찾기 : 두 개의 정수 n 및 k는,에서 k 개의 숫자의 가능한 모든 조합을 반환 감안할 때

1 2 3 ... n.

조합이 정렬되어 있는지 확인하십시오.

정교하게하려면, 모든 항목 내에서

1. 은 요소 분류되어야한다. [1, 4]는 유효한 항목이고 [4, 1]은 유효하지 않습니다.
2. 항목 자체 내에서 정렬해야합니다.

예 : n은, 용액 4, K = 2 = 경우

[
      [1,2]
      [1,3]
      [1,4]
      [2,3],691,363 (210)
      [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]