[C++/ Algorithm] 순열과 조합

순열

서로 다른 n개의 원소에서 r (단, 0< r ≤ n)개를 중복없이 순서를 고려하여 선택하거나 나열하거나 하는 것을 순열(permutation)이라고 합니다.

 

예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면

{1, 2, 3}

{1, 3, 2}

{2, 1, 3}

{2, 3, 1}

{3, 1, 2}

{3, 2, 1}

로 총 6가지가 나오게 됩니다. 

 

 

---

next_permutation 함수

C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있습니다. 기본적 문법은 다음과 같습니다. 

 

// default
bool next_permutation (BidirectionalIterator first, BiirectionalIterator last);

// custom
bool next_permutation (BidirectrionalIterator first, BidirectionalIterator last, Compare comp);

 

 

next_permutation은 순열을 구할 컨테이너(쉽게 말해 배열)의 시작과 끝 iterator를 인자로 받습니다.

만약 해당 컨테이너에 다음 순열이 존재하면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환하고, 다음 순열이 없다면 false를 반환합니다.

 

위 코드의 custom에서 볼 수 있듯이 비교 함수 comp를 인자로 넘기는 것도 가능합니다. 

---

next_permutation을 사용할 때는 몇 가지 주의할 점이 있습니다. 

1. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용가능합니다.
2. default로 operator < 를 사용해 순열을 생성합니다. 즉 오름차순으로 순열을 생성합니다. 
3. 중복이 있는 원소들은 중복을 제외하고 순열을 만들어줍니다. 

3번의 예시를 들자면 {0, 0, 1}과 같은 배열의 순열을 구한다면 중복을 제외한

{0, 0, 1}, {0, 1, 0}, {1, 0, 0}이 됩니다. 이를 이용해 조합(Combination)을 구할 수 있습니다. 

 

---

next_permutation 사용 예시 -> {1, 2, 3}의 모든 순열 출력하기

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

int main () {
	vector <int> v{1,2,3}; // {1,2,3} 요소를 가진 벡터선언
	sort(v.begin(), v.end()); // 오름차순으로 정리 (필수)
    
	do {
		for (int i = 0; i < v.end(); i ++) { // 배열 출력
        	cout << i << " ";
        }
    	cout << "\n"; // 한 배열 출력후 줄바꿈
	}while (next_permutation(v.begin(), v.end());
}

 

출력

 

 

재귀함수로 Permutation 함수 만들기

 

도식도

 

깊이 r에 도달하면 현재의 순열을 출력하고 반환합니다.

그렇지 않으면, 현재 위치 depth부터 마지막 위치까지의 각 요소를 한 번씩 선택하여 재귀적으로 순열을 생성합니다.

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

vector <int> v;

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

void f (int n, int r, int depth) {
	cout << n << " : " << r << " : " << depth << "\n";
    
	if (n == depth) {
		printV(v);
        return;
    }

	for (int i = depth; i < n; i ++) {
		swap(v[i], v[depth]);
        	f(n, r, depth + 1);
        	swap(v[i], v[depth]);
	}
}

int main () {
	for (int i = 1; i <= 3; i ++) {
		v.push_back(i);
    }
    f(3,3,0);
    return 0;
}

---

조합

서로 다른 n개의 원소에서 r (단, 0< r  ≤ n)개를 중복없이, 순서를 고려하지 않고 선택하는 것, 혹은 그 결과를 조합(combination)이라고 합니다.

 

순열은 순서가 중요했지만, 조합은 원소 r개를 뽑기만 하면 되기 때문에 순서가 중요하지 않습니다.

 

---

조합(Combination) 구하기

 

배열 s의 n개의 원소 중에서 r개의 원소를 택하는 방법은 다음과 같습니다. 

 

1. 우선 크기가 n인 배열 temp를 만들어 r개의 원소는 1로, (n-r)개의 원소는 0으로 초기화합니다. 
2. temp의 모든 순열을 구합니다. 
3. temp의 순열에서 원소값이 1인 인덱스만 배열 s에서 가져옵니다. 

temp에서 1이 있는 자리의 원소는 포함하고 0이 있는 자리의 원소는 미포함한다고 생각하면 쉽습니다. 이때 next_permutaion을 사용하면 오름차순으로 정렬되기 때문에, 조합은 내림차순으로 출력됩니다. 하지만 prev_permutation을 쓰면 모든 조합의 경우의 수를 오름차순으로 출력 가능합니다. 

 

※ prev_permutation은 내림차순 정렬된 데이터를 받아서 이전 순열로 바꿔줍니다. 

 

---

조합 사용예시

{1, 2, 3, 4} 중 2개의 원소를 고르는 모든 경우의 수 출력

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

int main () {
	vector <int> s{1,2,3,4};
	vector <int> temp{1,1,0,0};
    
    do {
    	for (int i = 0; i < s.size(); i ++) {
     		if (temp[i] == 1)
        		cout << s[i] << " ";
        }
        cout << '\n';
    }while (prev_permutation(temp.begin(), temp.end());
}

 

 

재귀함수로 구현하는 조합

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

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

void printV (vector <int> v) {
	for (int i : b) {
    	cout << i << " ";
    }
    cout << "\n";
}

void combi (int start, vector <int> v) {
	if (v.size() == k) {
		printV(v);
        return;
	}
    
    for (int i = start + 1; i < n; i ++) {
		v.push_back(i);
        combi(i, v);
        v.pop_back(i);
    }
}

int main () {
	vector <int> v;
    combi (-1, v);
    return 0;
}

 

 

중첩for문으로 만드는 조합

 

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

int main () {
    vector <int> b;
    //combi (-1, b);
    
    for (int i = 0; i < n; i++) { // i는 0 ~ n 까지 반복
        for (int j = 0; j < i; j ++) { // j는 0 ~ n-1까지 반복
            for (int k = 0; k < j; k ++) { // k는 0 ~ n-2까지 반복
                cout << i << " : " << j << " : " << k << "\n"; 
            }
        }
    }
}


/*
2 1 0
3 1 0
3 2 0
3 2 1
4 1 0
4 2 0
4 2 1
4 3 0
4 3 1
4 3 2

 

 

 

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

int main () {
    vector <int> b;
    //combi (-1, b);
    
    for (int i = 0; i < n; i++) { // i는 0 ~ n 까지 반복
        for (int j = i + 1; j < n; j ++) { // j는 0 ~ n-1까지 반복
            for (int k = j + 1; k < n; k ++) { // k는 0 ~ n-2까지 반복
                cout << i << " : " << j << " : " << k << "\n"; 
            }
        }
    }
}

/*
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

 

 

참고 사이트:http://www.cplusplus.com/reference/algorithm/

https://cplusplus.com/reference/algorithm/

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기

https://ansohxxn.github.io/algorithm/permutation/#google_vignette (재귀함수 순열)