[알고리즘] 순열과 조합

순열 (Permutation)

 먼저 위키피디아에서 순열의 정의를 찾아봤다. 

수학에서의 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이라고 설명한다.

순열은 Permutation 의 앞글자 P로 표현한다. 

 

n개의 원소를 가진 집합을 임의의 다른 순서로 섞는 연산의 경우의 수는 n! 과 같고, n개의 원소 중 r개의 원소를 선택하여 순열하는 경우의 수는 P(n, r)과 같다.

 

아래 이미지는 위키피디아에서 P(n, r) 연산하는 방법을 설명한 부분이다.

 

C++ 코드로 구현해보자.

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

using namespace std;

void func(){
	vector<int> v = {1, 2, 3};
    
	do{
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << " ";
        }
        cout << "\n";
    }while(next_permutation(v.begin(), v.end()));
}

 

위의 코드는 STL인 sort와 next_permutation (또는 sort+reverse와 prev_permutation)을 활용하여 원소가 n개인 집합을 순열 연산했다.

 

n개의 서로 다른 원소에서 r개를 선택하여 나열하는 코드도 작성해보자.

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

using namespace std;

void func(){ 
    vector<int> v = {1, 2, 3, 5, 4, 8, 7, 6};
    int r = 3;
    
    sort(v.begin(), v.end());
    
    do{
    	for(int i = 0; i < r; i++){
        	cout << v[i] << " ";
        }
        cout << "\n";
        
        reverse(v.begin() + r, v.end());
        
    }while(next_permutation(v.begin(), v.end()));
}

{1, 2, 3, 5, 4, 8, 7, 6} 의 집합에서 3개를 선택하여 나열하는 코드이다.

 

코드에선 r까지 출력했지만, 이미지에선 vector의 변화를 보기위해 v.size()까지 출력하였다.

첫 줄 sort를 통해 오름차순으로 정렬된 모습이 보인다.

 

reverse를 해주지 않아도 전체 경우의 수가 나오긴하지만, 필요한 r개 만큼만 출력하게 되면 사용한 이유를 알 수 있다.

 

재귀로 구현하는 방법과 더 자세한 설명은 아래 참고링크 (블로그) 에 있다.

---

 

조합 (Combination)

 조합도 위키피디아에서 정의를 먼저 읽어봤다.

조합은 n개의 집합에서 순서에 상관없이 r개를 선택하는 경우의 수이다.

수학 적으로는 C(n, r) 등으로 표현한다.

 

조합은 아래 방법으로 계산할 수 있으며, C(n, r) = C(n-1, r-1) + C(n-1, r) 가 성립한다.

 

위 공식을 활용해서 재귀로 코드를 작성해보자.

int combination(int n, int r) {
	if (n == r || r == 0) {
		return 1;
	}
	else {
		return combination(n-1, r-1) + combination(n-1, r);
	}
}

 

간단하게 작성됐다. 더 자세한 내용은 아래 (블로그) 부분을 참고하면 된다.

 

---

 

참고 자료 링크

• https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4 - 순열
• https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9 - 조합
• https://ansohxxn.github.io/algorithm/permutation/ - 순열 코드 (블로그)
• https://ansohxxn.github.io/algorithm/combination/ - 조합 코드 (블로그)