4. 순열, 조합

1.  모든 경우의 수를 나열하는 알고리즘.

2. 작은 범위의 문제에 대해서 완전 탐색 알고리즘에 적합.

 

조합

조합의 점화식 구하는 방법 : http://bitly.kr/nW9lZ

Combination, n개 중 k개를 고르는 방법의 수

조합 수 구하는 방법 :

#include <iostream>
using namespace std;
int Comb(int n, int r){
    //n개의 수중 r개 선택
    if(r==n){
        return 1;
    }else if(r==1){
        return n;
    }else{
        return Comb(n-1,r-1) + Comb(n-1, r);
    }
}

int main(){
    
    cout<<"5C1:"<<Comb(5,1)<<endl;   //5
    cout<<"5C2:"<<Comb(5,2)<<endl;   //10
    cout<<"5C3:"<<Comb(5,3)<<endl;   //10
    cout<<"5C4:"<<Comb(5,3)<<endl;   //10
    cout<<"5C5:"<<Comb(5,5)<<endl;   //1

    return 0;
}

조합 원소 구하는 방법 : http://hochulshin.com/permutation-composition-summary/

Algorithm - 순열과 조합

#include <iostream>
using namespace std;
char print_comb[10]; //nPr의 경우를 저장
char arr[10] = {'A','B','C','D','E','F','G','H','I'};

void PrintComb(int q){
    for(int i = q-1; i>= 0; i--){
        printf("%c ", print_comb[i]);
    }
    for(int i=0;i<q;++i){
        printf("%c ",print_comb[i]);
    }
    printf("\n");
}
//arr[]에서 앞에서부터 n개의 숫자 중 r개를 선택해서 조합을 출력하는 함수. q는 출력 시 출력 갯수 지정
void Comb(int n, int r, int q){
    if(r == 0){
        PrintComb(q);
        return;
    }else if(n<r){
        return;
    }
    else {  //loop이 아님
        print_comb[r-1] = arr[n-1];
        Comb(n-1, r-1, q);  //n-1Cr-1: 현재 아이템을 선택한 경우
        Comb(n-1, r, q);    //n-1Cr: 현재 아이템을 선택하지 않은 경우
    }
}

int main(){
    Comb(4, 2, 2);
//    D C C D
//    D B B D
//    D A A D
//    C B B C
//    C A A C
//    B A A B
    return 0;
}