조합 알고리즘

조합은 n개 중에 r개를 뽑는 경우의 수를 말한다.

순서를 생각하지 않고 단순히 뽑는 경우의 수!

사람 자리 선택 문제 같은 경우도 이와 비슷한데, 5개의 자리 중에서 4명의 사람이 앉는 경우의 수는?

이라는 문제가 존재한다고 생각하면, 5개중에서 4개를 선택하는 경우의 수라고 생각하면 된다.

이때 보통 수학에서   라고 표현을 한다. 

그러면 이를 컴퓨터에서는 어떻게 표현할 것인가가 문제인데...

위와 같이 접근을 한다고 한다.

5개중에서 4개를 고를 때 케이스를 이렇게 나눈다.

1.  A를 선택 해놓고 난 후, 3개를 선택  ==> A가 선택이 되었으니 선택할 수 있는 범위도 줄어들고,
    선택해야 할 갯수도 줄어 듬==> 

2.  A를 제외 해놓고 난 후, 4개를 선택 ==> A가 제외 되었으니 선택할 수 있는 범위는 줄어들고,
     선택해야 할 갯수는 그대로 임==>

그러면 이제 4개를 고른 모든 경우의 수가 되는 것이다. 그리고 다시 또 재귀적으로 반복해서 결과 값을 구한다.

1-1.   의 경우는 또 그러면, 이제 B를 선택해 놓고 난 후, 2개를 선택
        [이미 앞에서 A가 선택되었고,이제 B가 선택되었으니, 나머지 2개만 선택]

==> 

1-2.     의 경우는 또 그러면, 이제 B를 제외해 놓고 난 후, 3개를 선택

==> 

              

2-2. 의 경우는 4개 중에 4개를 선택해야 하는 경우의 수 : 1개

위와 같이 반복해서 값을 더하면 총 경우의 수를 구할 수 있다.

그리고 이 식을 간단하게 표현하면 다음과 같다.

위와 같이 나타내 진다.

조합의 총 합

 
#include <vector>
#include <iostream>
 
using namespace std;
int combination(int n, int r);
int main(void)
{
 
  int ret = 0;
  ret = combination(10,2);
 
  cout << ret << endl;
}
 
 
int combination(int n, int r){
 
  //n개중에  r(n)개를 뽑을 경우의 수는 1개
  //n개중에 0개를 뽑을 경우의 수는 1개
  if(n ==r || r == 0) return 1;
 
          //1개를 선택하고, 나머지 개를 선택    //1개를 제외하고, 나머지 개를 선택
  return combination(n-1,r-1)        +  combination(n-1,r);
}
 

조합의 총 겨우의 수

 
#include <vector>
#include <iostream>
 
using namespace std;
 
 
int b = 0;
//char arr[100][100] = {0};
static int n, r;
 
 
void save(char *array);
void combination( int n, int r, int index,int depth, char* array);
 
int main(void)
{
 
  char array[] = {0};
 
  cout << "Please enter an nCr n: ";
  cin >> n;
  cout << "Please enter an nCr r: ";
  cin >> r;
 
 
  combination(
     n, //n
     r, //r
     0, //index == 채웠는지 여부
     0, //poll에서 선택
     array);
 
  cout << b << endl;
}
 
void save(char *array){
 
    for(int i = 0 ; i < r; i++){
      cout << array[i] ;
    }
    cout << "\n" << endl;
 
 
}
 
 
void combination(int n, int r, int index, int depth, char* array){
 
      if(r == 0){
        save(array);;
        b++;
        return ;
      }
      //선택할 수 있는 전체 갯수 : n개
      //선택할 갯수 r개
      //선택할 갯수가 더 많으면  return;
      if(n < r)
        return;
 
 
      // 1개 선택
      // r-1개 선택
      // 다음 인덱스 증가 [채워진 배열]
      // poll 선택 이동
      array[index] = 'A'+depth;
      combination(n-1, r-1, index+1, depth+1, array);
 
      // 1개 제외
      // r개 선택
      // 인덱스  [채워진 배열]
      // poll 선택 이동
      combination(n-1, r, index, depth+1,array);
 
      return;
 
 
}
 

[참고,출처] : http://gorakgarak.tistory.com/523