[c++] 알고리즘 개념공부 :: 순열과 조합 (코드, next_permutation 이용, 직접 구현)

순열과 조합

순열

정의

순열은 중복없이 n개 중 r개를 뽑아 순서를 정해 나열하는 경우이다. 위의 그림처럼 A, B, C 세가지 원소가 있을 때, 2개를 뽑아 순서를 정하는 것을 3P2라고 한다. 아래와 같은 경우의 수가 나오므로 총 6가지 이다.

순열은 P(Permutation)로 표현하며 식은 다음과 같다.
$$
{}n\mathrm{P}{r} = \frac{n!}{(n-r)!}
$$

중복 순열이라는 특별한 경우는 순열 중 같은 종류의 것을 다시 뽑을 수 있는 경우를 말한다.

중복 순열은 Π로 표현하며 식은 다음과 같다.
$$
{n}\mathrm{\pi}{r} = n^r
$$

 

구현

순열

// 직접 구현
void swap(vector<int>& set, int a, int b){
    int tmp = set[a];
    set[a] = set[b];
    set[b] = tmp;
}

void permutation(vector<int>& set, int size, int n, int r){
    if(size==r){
        for(int i=0; i<size; i++)
            cout << set[i] << " ";
        cout << endl;
        return;
    }
    for(int i=size; i<n; i++){
        swap(set, i, size);
        permutation(set, size+1, n, r);
        swap(set, i, size);
    }
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);

    combination(set, 0, 3, 2);

    return 0;
}

// next_permutation 이용
void permutation(vector<int>& set, int n, int r){
    do{
        for(int i=0; i<r; i++)
            cout << set[i] << " ";
        cout << endl;
    }while(next_permutation(set.begin(), set.end()));
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);

    combination(set, 3, 2);

    return 0;
}

 

중복 순열

void repeatedPermutation(vector<int>& set, vector<int>&tmp, int size, int n, int r){
    if(size==r){
        for(int i=0; i<size; i++)
            cout<< tmp[i] << " ";
        cout << endl;
        return;
    }
    for(int i=0; i<n; i++){
        tmp[size] = set[i];
        permutation(set, tmp, size+1, n, r);
        tmp[size] = 0;
    }
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);
    vector<int>tmp(3);

    repeatedPermutation(set,tmp,0, 3, 2);

    return 0;
}

중복 순열을 구하기 위해서 tmp라는 vector를 하나 더 사용하였다. 따로 vector를 사용하지 않고도 구현할 수 있는 방법이 있을까?

 

조합

정의

조합은 중복없이 n개 중 r개를 순서에 상관없이 뽑는 경우이다. 위의 그림처럼 A, B, C 세가지 원소가 있을 때, 2개를 순서에 상관없이 뽑는 것을3C2라고 한다. 아래와 같은 경우의 수가 나오므로 총 3가지이다.

조합은 C(Combination)로 표현하며 식은 다음과 같다.
$$
{n}\mathrm{C}{r} = \frac{{n}\mathrm{P}{r}}{r!} \ ({n}\mathrm{C}{0},\ {n}\mathrm{C}{n}은\ 0)
$$

$$
{n}\mathrm{C}{r} = {n-1}\mathrm{C}{r-1}+{n-1}\mathrm{C}{r}
$$
중복 조합이라는 특별한 경우는 조합 중 같은 종류의 것을 다시 뽑을 수 있는 경우를 말한다.

중복 조합은 H로 표현하며 식은 다음과 같다.
$$
{n}\mathrm{H}{r} = {n+r-1}\mathrm{C}{r}
$$

$$
{n}\mathrm{H}{r} = {n}\mathrm{H}{r-1} +{n-1}\mathrm{H}{r}
$$

 

구현

조합

// 직접 구현
void swap(vector<int>& set, int a, int b){
    int tmp = set[a];
    set[a] = set[b];
    set[b] = tmp;
}

void combination(vector<int>& set, int idx, int size, int n, int r){
    if(size==r){
        for(int i=0; i<size; i++)
            cout << set[i] << " ";
        cout << endl;
        return;
    }
    for(int i = idx; i<n; i++){
        swap(set, i, size);
        combination(set, i+1, size+1, n, r);
        swap(set, i, size);
    }
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);

    combination(set, 0, 0, 3, 2);

    return 0;
}

// next_permutation 이용
void combination(vector<int>& set, vector<int>& tmp, int n, int r){
    do{
        for(int i=0; i<n; i++){
            if(tmp[i]==1)
                cout << set[i] << " ";
        }
        cout << endl;
    }while(next_permutation(tmp.begin(), tmp.end()));
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);

    vector<int> tmp;
    tmp.push_back(0);
    tmp.push_back(1);
    tmp.push_back(1);
    // 주의!! 0, 1, 1 오름차순 순서로 써야 next_permutation이 작용한다.
    // 아니면 내림차순 정렬 후 prev_permutation도 가능

    combination(set, tmp, 3, 2);

    return 0;
}

 

중복 조합

void repeatedCombination(vector<int>& set, vector<int>& tmp, int size, int index, int n, int r){
    if(size==r){
        for(int i=0; i<size; i++)
            cout << tmp[i] << " ";
        cout << endl;
        return;
    }

    for(int i=index; i<n; i++){
        tmp[size] = set[i];
        repeatedCombination(set, tmp, size+1, i, n, r);
    }
}

int main()
{
    vector<int> set;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);

    vector<int> tmp(3);

    repeatedCombination(set, tmp, 0, 0, 3, 2);

    return 0;
}

 

관련 문제

Gaaaaaaaaaarden