순열과 조합

Algorithm Theory

By Minssuy99

Posted 2025/01/22

views 8 min read

순열과 조합

순열

\[\begin{equation} ^nP_r = \frac{n!}{(n-r)!} \label{eq:permutation} \end{equation}\]

개념

순열이란 순서와 상관 있게 뽑아 나열한 집합이다.

n 개의 원소 중에서 r 개를 뽑아 순서를 고려하여 나열하는 방법을 의미한다.

{1, 2, 3} 배열에서 3개의 숫자를 순열로 뽑는다고 하면 아래와 같다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

만약 2개의 숫자를 순열로 뽑는다면 아래와 같다.

문제에서 아래와 같은 말이 있다면 순열로 풀면 된다.

순서를 재배치하여
~~ 한 순서의 경우 max 값

C++ 의 <algorithm> 헤더에는 next_permutation 이라는 함수를 제공한다.

주어진 범위의 순열을 다음 사전순 순열로 바꿔주는 함수이다.

쉽게 말하자면 1 2 3 인 상태인 함수에서 next_permutation 을 사용하면 1 3 2 가 된다.

함수 시그니처

  
next_permutation(BidirectionalIterator first, BidirectionalIterator last);

first : 순열의 시작을 나타내는 반복자.
last : 순열의 끝을 나타내는 반복자.

{1, 2, 3} 이라는 배열이 있다면, 파라미터엔 (0, 3) 을 기입하면 된다.

last 자리에는 배열의 마지막 인덱스 + 1 을 해줘야 하는 것을 유의하자.

한가지 더 유의해야 할 것은, next_permutation 을 사용하기 위해선 배열이 오름차순으로 되어있어야 한다.

번외로, prev_permutation 이 있는데, 이건 내림차순의 배열을 기반으로 순열을 만들 수 있다.

예시

  


#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int array[] = {1, 2, 3};

    do
    {
        for (int i : array)
        {
            cout << i << " ";
        }
        cout << '\n';
    } while (next_permutation(array, array + 3));

}

vector 를 사용할 땐 begin 과 end 를 사용하면 된다.

  


vector<int> vec = {1, 2, 3};
do
{
    for (int i : a)
    {
        cout << i << " ";
    }
    cout << '\n';
} while (next_permutation(vec.begin(), vec.end()));

/* Console */
2 3
3 2
1 3
3 1
1 2
2 1

vector 를 sort 로 오름차순 정렬 후, 앞에서 2개의 원소만 출력하는 코드이다.

  


vector<int> vec = {2, 1, 3, 100, 200};

sort(vec2.begin(), vec.end());

do
{
    for (int i = 0; i < 2; i++)
    {
        {
            cout << vec[i] << " ";
        }
    }
    cout << '\n';
} while (next_permutation(vec.begin(), vec.end()));

구현

permutation 함수를 직접 구현해보고 재귀의 흐름을 이해한다.

  


void makePermutation(int n, int r, int depth, vector<int> &vec)
{
    if (r == depth) // 기저사례
    {
        print(vec);
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(vec[i], vec[depth]);
        makePermutation(n, r, depth + 1, vec); // 재귀호출
        swap(vec[i], vec[depth]); // 스택 프레임에 의해 실행 후 재귀 종료
    }
    return;
}

위의 사진은 흐름도를 깔끔하게 정리한 것 뿐이고, 이걸 보고 이해되진 않았다.

디버깅을 해도 이해가 되지않아서, 흐름을 손으로 직접 그려보면서 이해했다.

Complete Code

  


#include <bits/stdc++.h>

using namespace std;

void print(vector<int> &vec)
{
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << " ";
    }
    cout << "\n";
}

void makePermutation(int n, int r, int depth, vector<int> &vec)
{
    if (r == depth) // base case
    {
        print(vec);
        return;
    }

    for (int i = depth; i < n; i++)
    {
        cout << "[Current state : " << "i = " << i << "depth = " << depth << "]\n"; // debug code

        cout << "Swap " << i << " and " << depth << ".\n"; // debug code
        swap(vec[i], vec[depth]);
        makePermutation(n, r, depth + 1, vec);

        cout << "Swap " << i << " and " << depth << " back.\n"; // debug code
        swap(vec[i], vec[depth]);
    }
    return;
}

int main()
{
    vector<int> vec = {1, 2, 3};
    makePermutation(3, 3, 0, vec);

    return 0;
}

조합

\[\begin{equation} ^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!} \label{eq:combination} \end{equation}\]

개념

조합이란 순서에 관계없이 나열한 집합이다.

n 개의 원소 중에서 r 개를 뽑아 순서에 관계없이 나열하는 방법을 의미한다.

{1, 2, 3} 배열에서 3개의 숫자를 조합으로 뽑는다고 하면 아래와 같다.

1 2 3

순열과 다르게 조합에선 단 1개만 나온다.

\[\begin{equation} ^3C_3 = \binom{3}{3} = \frac{3!}{3!(3-3)!} = 1 \label{eq:example_combination} \end{equation}\]

(3 - 3)! = 0! 이므로, 0! = 1 이다.

즉 3! / 3! = 1 이라는 값이 나온다.

조합을 구현하는 방법에는 재귀함수, 혹은 중첩 for 문으로 구현하는 방법이 있다.

4개이상 뽑는건 재귀함수가 좋고 3개 이하는 중첩 for문으로 구현하는 것이 편리하다.

구현

Use For Loop

  


#include <bits/stdc++.h>
using namespace std;

int n = 5;
int k = 3;
int a[5] = {1, 2, 3, 4, 5};

int main()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                cout << i << " " << j << " " << k << '\n';
            }
        }
    }
    return 0;
}

Use Recursion

  


#include <bits/stdc++.h>

using namespace std;

int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};

void print(vector<int> vec)
{
    for (int i : vec)
        cout << i << " ";
    cout << '\n';
}

void combination(int start, vector<int> vec)
{
    if (vec.size() == k) // 기저사례
    {
        print(vec);
        return;
    }
    for (int i = start + 1; i < n; i++)
    {
        vec.push_back(i);
        combination(i, vec);
        vec.pop_back(); // 원복
    }
    return;
}

int main()
{
    vector<int> vec;
    combination(-1, vec);
    return 0;
}

/* Console */
1 2
1 3
1 4
2 3
2 4
3 4
2 3
2 4
3 4
3 4

Theory, Algorithm