순열, 조합 구하는 알고리즘

순열, 조합

다들 고등학교 때 배우는 순열과 조합에 대한 내용이다.
당연하지만 공식을 다루기 보다는 어떻게 코드로 순열과 조합을 구현할 수 있을까에 대한 내용이다.

1. 순열

n개의 원소가 있다고 할 때 그중에 r개를 뽑아서 나열하는 경우의 수이다.
다 배워서 알겠지만 공식은 아래와 같다.

\[_{n}P_{r} = \frac{n!}{(n-r)!}\]

만약 N개의 원소를 모두 사용해서 순열을 구하면 분모가 0!이 되므로 1이된다.
따라서 우리가 잘 알고 있는 $n!$ 이 된다.

이를 코드를 구현하면 아래와 같다.
재귀 함수와 SWAP으로 구현했다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void permutation(vector<int>& arr,int dept, int n, int r) {
    if(dept == r) {
        for(int i=0;i<r;i++) {
            cout << arr[i] <<" ";
        }
        cout << endl;

        return;
    }

    for(int i=dept;i<n;i++) {
        swap(arr[dept],arr[i]);
        permutation(arr,dept+1,n,r);
        swap(arr[dept],arr[i]);
    }
}

int main() {
    vector<int> arr = {1,2,3,4};
    permutation(arr,0,4,3);
}

※ 코드 해석

main 코드에서 permutation을 호출할때 먼저 순열을 구할 배열과, 현재 위치, 배열의 길이, 몇 개를 뽑아서 나열할건지 순서대로 인자를 넣는다. 각각 arr, dept, n, r이다.

첫번째 조건문인 if(dept == r) 는 뽑은 개수가 최대 뽑으려는 개수까지 도달했을 때 현재 선택된 순서를 출력하고 종료하는 분기문이다.
모두 순열을 반환하는데 그 중에서 앞에서 r까지만 반환하여 r개를 뽑아서 배치하는 순서를 표현한 것이다. 보면 알테니 별다른 설명을 첨언하지는 않겠다.

그 다음에 for문이 중요한데, SWAP을 먼저 arr[i]와 arr[dept]간에 한번 하고 permutation을 그 다음 순서로 호출하고, 했던 SWAP을 다시 호출한다. 처음 dept가 0,i가 0일때는 동일한 값을 SWAP하는 것이라 변함이 없지만, for 문이 구동되어 i가 dept+1일때부터는 값이 변경된다.

이렇게 SWAP을 하고 함수 호출 뒤 다시 SWAP을 하면 arr의 index의 가장 n에 가까운 곳까지 간 뒤 하나씩 SWAP되고 다시 SWAP되어 원래 대로 돌아오는게 반복된다.
가장 첫번째 진입했던 for가 완료될때 이미 dept==r이었을때 결과가 모두 표기되면서 함수가 종료된다.

아래는 r을 n과 같이 4로 두고 호출했을때의 결과이다.
위 함수와 대조해보면 이해하기 쉬울 것이다.

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 3 2 
1 4 2 3 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 3 1 
2 4 1 3 
3 2 1 4 
3 2 4 1 
3 1 2 4 
3 1 4 2 
3 4 1 2 
3 4 2 1 
4 2 3 1 
4 2 1 3 
4 3 2 1 
4 3 1 2 
4 1 3 2 
4 1 2 3

2. 조합

n개의 원소가 있다고 할 때 그중에 r개를 뽑는 경우의 수이다. 순열과는 달리 순서는 고려하지 않고 동일한 원소가 있다면 같은 것으로 친다.
조합의 경우의 수는 아래와 같다.

\[_{n}C_{r} = \frac{n!}{r!(n-r)!}\]

조합을 구현하는 코드는 아래와 같다.
어떤 원소를 뽑은 경우와 안 뽑은 경우를 두고 재귀 함수로 구현했다.

#include<iostream>
#include<vector>
#include<algorithm>
#define R 3

using namespace std;


void combination(vector<int> arr,vector<int> comb, int r,int dept,int index) {
    if(r == 0) {
        for(int i=0;i<size(comb);i++)
            cout << comb[i] << " ";
        cout << endl;
        return;
    }
    else{
        comb[index] = arr[dept];
        combination(arr,comb,r-1,dept+1,index+1);

        combination(arr,comb,r,dept+1,index);
    }
}


int main() {
    vector<int> arr = {1,2,3,4};
    vector<int> comb(R);
    
    combination(arr,comb,R,0,0);
}

※ 코드 해석

순열과 동일하게 재귀 함수로 구현했다.
처음 arr 배열은 조합을 구하고자하는 배열이고, comb는 조합을 담아둘 배열이다. r은 몇 개를 뽑을 지, dept는 현재 arr에서 어디를 보고 있는지? index는 comb의 어디 위치에 값을 넣을 건지에 대한 인자이다.

처음에 호출할때는 dept와 index 둘다 0으로 호출한다.
combination 함수 안에는 총 2개의 분기문으로 되어있는데 r==0 즉 뽑을 개수만큼 다 뽑은 경우와 덜 뽑아서 더 뽑아야되는 경우이다. 사실 r이 arr의 길이보다 더 큰 경우도 고려해주어야하지만 그런 예외처리는 여기서 다루지 않겠다. 굳이 예외처리 해야겠다면
else if를 추가해서 dept == size(arr) 를 조건으로 두고 return 해버리면 된다.

덜 뽑은 경우에도 두 가지로 나뉜다. 현재 arr[dept]값을 뽑을 것이냐 아니면 뽑지 않을 것이냐이다.
만약 arr[dept]값을 뽑았다면 combination(arr,comb,r-1,dept+1,index+1); 부분이고 뽑지 않았다면 combination(arr,comb,r,dept+1,index); 이다. 왜냐면 index 값의 변경이 없기 때문에 함수 호출시 index 값을 dept+1로 덮어쓰기 때문이다.

3. 빠르게 가져다 쓰기

실무에서 순열 혹은 조합을 구현해야한다고 하면 위에 두 개의 코드 처럼 구현하고 있을 시간이 없다.
대부분 그냥 Stack Overflow를 긁어서 쓰거나 혹은 AI에게 맡기고 몇번 테스팅해본 뒤 그냥 고개를 끄덕이며 쓸 것이다.
만약 쓰려는 언어가 CPP라면 검증된 함수가 이미 존재한다.

바로 next_permutation이라는 함수이며 c++ 20에서 추가된 함수이다. 이 함수를 쓰기 위해서는 아래의 2가지를 주의해야한다.

1. 오름차순으로 정렬되었을때만 사용가능
2. 중복이 있는 원소들은 중복을 제거

함수의 기본 타입은 아래와 같다.

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

별도의 compare 함수를 넣지 않으면 기본적으로 <, 즉 오름차순으로 순열을 생성한다.

1) 순열

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s = "ABCD";
    
    do {
        std::cout << s << '\n';
    } while (std::next_permutation(s.begin(), s.end()));
}

위 코드를 실행시키면 아래와 같은 출력이 나온다.

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

2) 조합

위 next_permutation을 응용하여 조합 함수를 쉽게 구현할 수 있을까?
가능하다. 순열 코드에서 어떤 값을 꺼냈고, 안 꺼냈고를 선택하게 추가하면 된다.
순열 예시에서 2개를 뽑는 조합 코드로 변경하면 아래와 같다.

여기서 pickup은 오름차순으로 0부터 시작해서 총 뽑고싶은 개수만큼 1을 뒤에서 부터 채워주면 된다.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::string s = "ABCD";
    std::vector<int> pickup = {0,0,1,1};
    
    do {
        for(int i=0;i<size(s);i++) {
            if(pickup[i] == 1)
                std::cout << s[i];
        }
        std::cout << std::endl;
    } while (std::next_permutation(pickup.begin(), pickup.end()));
}

위 코드를 실행시키면 아래와 같은 결과가 나온다.

CD
BD
BC
AD
AC
AB

참고 자료

• 위키백과 - 순열
• 위키백과 - 조합
• cppreference - next_permutation