[c++] 순열, 중복순열, 조합, 중복조합

순열

순서가 존재하고 숫자가 중복되면 안 됨

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

int number = 3;
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 6;

vector<int> path(number, 0);
bool visited[MAX_NUMBER + 1];

void print()
{
    for (int i : path)
        printf("%d ", i);
    printf("\n");
}

void permutation(int level)
{
    if (level == number)
    {
        print();
        return;
    }

    for (int i = MIN_NUMBER; i <= MAX_NUMBER; i++)
    {
        if (visited[i])
            continue;
        visited[i] = true;
        path[level] = i;
        permutation(level + 1);
        visited[i] = false;
    }
}

int main(void)
{
    permutation(0);
}

 

중복순열

순서가 존재하고 숫자가 중복될 수 있음

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

int number = 3;
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 6;

vector<int> path(number, 0);

void print()
{
    for (int i : path)
        printf("%d ", i);
    printf("\n");
}

void permutationWithRepetition(int level)
{
    if (level == number)
    {
        print();
        return;
    }

    for (int i = MIN_NUMBER; i <= MAX_NUMBER; i++)
    {
        path[level] = i;
        permutationWithRepetition(level + 1);
    }
}


int main(void)
{
    combinationWithRepitition(0);
}

 

조합

순서가 존재하지 않고 숫자가 중복되면 안 됨

#include <iostream>
#include <vector>

using namespace std;

int number = 3;
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 6;

vector<int> path(number, 0);

void print()
{
    for (int i : path)
        printf("%d ", i);
    printf("\n");
}

void combination(int level, int idx)
{
    if (level == number)
    {
        print();
        return;
    }

    for (int i = idx; i <= MAX_NUMBER; i++)
    {
        path[level] = i;
        combination(level + 1, i + 1);
    }
}

int main(void)
{
    combination(0, MIN_NUMBER);
    return 0;
}

 

중복조합

순서가 존재하지 않고 숫자가 중복될 수 있음

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

int number = 3;
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 6;

vector<int> path(number, 0);

void print()
{
    for (int i : path)
        printf("%d ", i);
    printf("\n");
}

void combinationWithRepitition(int level, int idx)
{
    if (level == number)
    {
        print();
        return;
    }

    for (int i = idx; i <= MAX_NUMBER; i++)
    {
        path[level] = i;
        combinationWithRepitition(level + 1, i);
    }
}

int main(void)
{
    combinationWithRepitition(0, MIN_NUMBER);
}

 

number : 순열/조합을 몇 개 선택할 건지

MIN_NUMBER : 선택하려는 연속하는 숫자 중 가장 작은 숫자

MAX_NUMBER : 선택하려는 연속하는 숫자 중 가장 큰 숫자

 

세 변수를 상황에 맞게 수정해서 응용 가능하다