[알고리즘] 조합, 순열, 부분 집합

조합

#include <iostream>
using namespace std;

const int n = 5;
const int r = 3;
int arr[n] = {1, 2, 3, 4, 5};
int sel[r];

//출력
void printSel() {
    for (int i = 0; i < r; ++i)
        printf("%d ", sel[i]);
    printf("\n");
}

// nCr
void comb(int idx, int sidx) {
    if (sidx == r) {
        printSel();
        return;
    }
    for (int i = idx; i <= n - (r - sidx); ++i) {
        sel[sidx] = arr[i];
        comb(i + 1, sidx + 1);
    }
}

int main(void) {
    comb(0, 0);
    return 0;
}

중복 조합

#include <iostream>
using namespace std;

const int n = 5;
const int r = 3;
int arr[n] = {1, 2, 3, 4, 5};
int sel[r];

//출력
void printSel() {
    for (int i = 0; i < r; ++i)
        printf("%d ", sel[i]);
    printf("\n");
}

// nHr
void combRep(int idx, int sidx) {
    if (sidx == r) {
        printSel();
        return;
    }
    for (int i = idx; i < n; ++i) {
        sel[sidx] = arr[i];
        combRep(i, sidx + 1);
    }
}

int main(void) {
    combRep(0, 0);
    return 0;
}

순열

평범한 방식

#include <iostream>
using namespace std;

const int n = 5;
const int r = 3;
int arr[n] = {1, 2, 3, 4, 5};
bool use[n];
int sel[r];

//출력
void printSel() {
    for (int i = 0; i < r; ++i)
        printf("%d ", sel[i]);
    printf("\n");
}

// nPr
void perm(int idx) {
    if (idx == r) {
        printSel();
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!use[i]) {
            sel[idx] = arr[i];
            use[i] = true;
            perm(idx + 1);
            use[i] = false;
        }
    }
}

int main(void) {
    perm(0);
    return 0;
}

swap 방식

구현이 간단하다, 오름차순으로 정렬되지 않는다

#include <iostream>
using namespace std;

const int n = 5;
const int r = 3;
int arr[n] = {1, 2, 3, 4, 5};

//출력
void printSel() {
    for (int i = 0; i < r; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

// nPr
void perm(int idx) {
    if (idx == r) {
        printSel();
        return;
    }
    for (int i = idx; i < n; ++i) {
        swap(arr[idx], arr[i]);
        perm(idx + 1);
        swap(arr[idx], arr[i]);
    }
}

int main(void) {
    perm(0);
    return 0;
}

중복 순열

#include <iostream>
using namespace std;

const int n = 6;
const int r = 9;
int arr[n] = {1, 2, 3, 4, 5};
int sel[r];

//출력
void printSel() {
    for (int i = 0; i < r; ++i)
        printf("%d ", sel[i]);
    printf("\n");
}

// nΠr
void permRep(int idx) {
    if (idx == r) {
        printSel();
        return;
    }
    for (int i = 0; i < n; ++i) {
        sel[idx] = arr[i];
        permRep(idx + 1);
    }
}

int main(void) {
    permRep(0);
    return 0;
}

부분 집합

비트마스킹

#include <iostream>
using namespace std;

const int n = 5;

//원소의 개수가 n인 부분 집합
int main(void) {
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j)
            if ((i & (1 << j)) != 0)
                printf("1");  //뽑았을 때
            else
                printf("0");  //안 뽑았을 때
        printf("\n");
    }
    return 0;
}