집합 n의 모든 부분 집합 r의 목록을 생성하려고합니다. 내 코드는 n-r = 2 인 경우 작동하지만> 2 인 경우 잘못된 출력을 인쇄합니다.

Question

집합에서 부분 집합의 목록을 생성하려고합니다. 예를 들어, 나는 = 4, 나는 다음과 같은 것이 15 개 가능한 조합했을 N = 6, R이 있다면 :

가

0 1 2 3 
0 1 2 4 
0 1 2 5 
0 1 3 4 
0 1 3 5 
0 1 4 5 
0 2 3 4 
0 2 3 5 
0 2 4 5 
0 3 4 5 
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5 

내 현재 코드는 위의 부분 집합으로 작동 하는가를하는 경우 N = 6 & R = 4. nr = 2의 다른 조합이있는 경우에도 작동합니다. 그것은 다른 무엇을 위해 작동하지 않으며 나는 내 코드가 나에게 완벽하게 이해하기 때문에 디버깅 문제가 조금있다.

int array[r]; 
int difference = n-r; 

for(int i = 0; i < r; i++){ 
    array[i] = i; 
} 

while (array[0] < difference){ 
     print (array, r); 
     for(int i = r-1; i >= 0; i--){ 
      if ((array[i] - i) == 0){ 
       array[i] = array[i] + 1; 
       for (int j = i+1; j < r; j++){ 
        array[j] = j + 1; 
       } 
       i = r; 
      } 
      else{ 
       array[i] = array[i] + 1; 
      } 
      print (array, r); 
     } 
    } 
} 

일부 컨텍스트를 제공하기 위해, I = 6 및 R = 3, I는 출력으로 20 개 조합을 가정하고 N에 연결하면 : 내가 가진 코드는 다음과 같다. 그러나 단 14 인쇄됩니다 :

0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

첫 번째 및 마지막 출력을 올바르게 인쇄 할 수 있지만 모든 출력을 인쇄해야합니다. 3 번째 반복 후에 코드가 0 1 4에서 0 2 3으로 진행될 때 실패하기 시작합니다. 대신 0 1 5로 이동해야합니다. 내가 뭘 잘못하고 있는지에 대한 제안은?

Answer 1

다음은 내가하려는 것입니다. 내가 알 수있는 한, 주된 문제는 배열 요소를 계속 증가시키기보다는 유효한 값으로 증가시킨 후 루프가 처음부터 다시 시작해야한다는 것입니다.

이 버전은 break을 사용하여 for 루프에서 빠져 나와야 만 한 곳에서 print을 호출합니다. 또한 발견 된 조합을 계산합니다.

#include <iostream> 

void print(int array[], int r) { 
    for(int i=0; i<r; ++i) { 
     std::cout << array[i] << ' '; 
    } 
    std::cout << '\n'; 
} 

int main() { 
    static const int n = 6; 
    static const int r = 3; 

    static const int difference = n-r; 
    int array[r]; 
    for(int i = 0; i < r; i++) { 
     array[i] = i; 
    } 
    int count = 0; 
    while(array[0] <= difference) { 
     ++count; 
     print(array, r); 
     for(int i=r-1; i>=0; --i) { 
      ++array[i]; 
      if(array[i] <= difference + i) { 
       for(int j=i+1; j<r; ++j) { 
        array[j] = array[j-1] + 1; 
       } 
       break; 
    } } } 
    std::cout << "count: " << count << '\n'; 
} 

출력 아마

0 1 2 
0 1 3 
0 1 4 
0 1 5 
0 2 3 
0 2 4 
0 2 5 
0 3 4 
0 3 5 
0 4 5 
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
count: 20