완전탐색_순열/중복순열/조합/중복조합

순열(Permutation)

- n개 중 r개를 선택할 때, 순서를 고려하고 중복을 허용하지 않는 방법

- nPr = n!/(n-r)!

- 재귀적으로 배열을 채워나가면서 중복하는 숫자가 없도록 check 배열을 업데이트

 

#include <vector>
#include <iostream>
using namespace std;

//순열: 순서 O, 중복 X
//nPr = n!/(n-r)!

#define n 3
#define r 2

int arr[30];
int check[30];

void printarr() {

    for (int i=0; i<r; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

void permutation(int k) {

    if (k == r) {
        printarr();
        return ;
    }

    for (int i=0; i<n; i++) {
        if (check[i]) continue;
        check[i] = true;
        arr[k] = i;
        permutation(k+1);
        check[i] = false;
    }
}

int main() {

    permutation(0);
    return 0;
}

 

 

중복순열(Permutation with Repetition)

- n개에서 r개를 택할 때, 순서를 고려하고 중복을 허용하는 방법

- nπr = n^r (r개의 자리에 모두 n개의 숫자가 올 수 있으므로 n의 r제곱만큼의 경우의 수를 가짐)

- 순열과 비슷하게 구현하되, 중복을 확인하는 check 배열 불필요

 

#include <vector>
#include <iostream>
using namespace std;

//중복 순열: 순서 O, 중복 O
//nπr = n^r

#define n 3
#define r 2

int arr[30];

void printarr() {

    for (int i=0; i<r; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

void permutationWithRep(int k) {

    if (k == r) {
        printarr();
        return ;
    }

    for (int i=0; i<n; i++) {
        arr[k] = i;
        permutationWithRep(k+1);
    }
}

int main() {

    permutationWithRep(0);
    return 0;
}

 

 

조합(Combination)

- n개에서 r개를 택할 때, 순서를 고려하지 않고 중복도 허용하지 않는 방법

- nCr = n!/(n-r)!r!

- 배열을 채울 때 배열의 원소가 이전 자리 수보다 크도록 구현

 

#include <vector>
#include <iostream>
using namespace std;

//조합: 순서 X, 중복 X
//nCr = n!/(n-r)!r!

#define n 3
#define r 2

int arr[30];

void printarr() {

    for (int i=0; i<r; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

void combination(int k) {

    if (k == r) {
        printarr();
        return ;
    }

    int st = 0;
    if (k != 0) st = arr[k-1]+1;
    for (int i=st; i<n; i++) {
        arr[k] = i;
        combination(k+1);
    }
}

int main() {

    combination(0);
    return 0;
}

 

 

중복 조합(Combination with Repetition)

- n개에서 r개를 택할 때, 순서를 고려하지 않고 중복을 허용하는 방법

- nHr = (n+r-1)Cr

- 배열에 원소를 채울 때 배열의 원소가 이전 자리 수보다 크거나 같도록 구현

 

#include <vector>
#include <iostream>
using namespace std;

//중복조합: 순서 X, 중복 O
// nHr = (n+r-1)Cr

#define n 3
#define r 2

int arr[30];

void printarr() {

    for (int i=0; i<r; i++) cout<<arr[i]<<" ";
    cout<<endl;
}

void CombinationWithRep(int k) {

    if (k == r) {
        printarr();
        return ;
    }

    int st = 0;
    if (k != 0) st = arr[k-1];
    for (int i=st; i<n; i++) {
        arr[k] = i;
        CombinationWithRep(k+1);
    }
}

int main() {

    CombinationWithRep(0);
    return 0;
}