오늘의 공부

순열, 조합 구현

C++로 순열과 조합을 구현해보았다.

순열은 STL의 next_permutation과 prev_permutation을 쓰면 쉽게 구현할 수 있긴 하다. 하지만 하다보면 해당 원리를 이용해 조금 변형할 일이 생기기 마련...... 

순열과 조합은 보통 재귀를 이용해 구현한다. 

◎ 조합

조합은 순열과 다르게 순서가 없는 나열이다. 그러니까 원소들을 중복 없이 뽑는다.

조합을 먼저 쓴 이유는 조합을 먼저 구해야 순열을 구할 수 있다. 

우선 조합은 nCr로 n개 중에 r개를 뽑는 것이다.

만약 배열 {1,2,3,4,5}의 원소 중 3개씩 뽑는 조합을 만든다 했을 때 나올 수 있는 경우의 수는

(1,2,3) (1,2,4) (1,2,5) (1,3,4) (1,3,5) (1,4,5)

(2,3,4) (2,3,5) (2,4,5)

(3,4,5)
로 총 10개가 된다.

조합의 공식이 nPr / r! 임을 생각해보면 10개가 맞다. 

#include <iostream>
using namespace std;


void Combination(int arr[], int n, int r,  int index,int target, int comb_arr[])
{
	if (r == 0)
	{
		// r개를 뽑기로 했는데 r개를 다 뽑은 경우
		for (int i = 0; i < index; ++i)
		{
			cout << comb_arr[i];
		}
		cout << endl;
	}
	else if (target == n)
	{
		// target이 index를 초과=>종료 
		return;
	}
	else
	{
		//target 인덱스의 원소를 저장
		comb_arr[index] = arr[target];
		Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); // 해당 원소를 선택
		Combination(arr, n, r, index, target + 1, comb_arr); // 해당 원소를 선택하지 않음
	}
}

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	int n = 5;
	int r = 3;

	int* comb_arr = new int[5];
	
	Combination(arr, 5, 3, 0,0 , comb_arr);
}

조합을 하기 위해서 배열을 돌면서 뽑는 경우와 안 뽑는 경우를 조사한다. 

comb_arr는 빈 배열로 Combination 함수를 돌면서 뽑은 원소를 저장하는 배열이다.

Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); // 해당 원소를 선택
Combination(arr, n, r, index, target + 1, comb_arr); // 해당 원소를 선택하지 않음

왜 두번 호출을 하냐면..

이 부분을 보면 위의 줄은 target에 위치한 원소를 원소를 뽑는 부분, 밑의 줄은 원소를 선택하지 않는 부분이다.

또한 target은 함수 호출 시 항상 1을 증가시켜서 넘겨야 순회하는 역할을 할 수 있다.

선택할 때는 r을 1 감소시키고 index를 1 증가시키며 선택하지 않을 때는 r을 그대로, index도 그대로 넣고 호출한다.

index를 증가시키는 이유는 현재 target이 가리키는 원소를 선택하고 다음 index를 선택하기 위함이며

증가시키지 않는 것은 현재 target이 가리키는 원소를 선택하지 않고 현재 index에 다른 원소를 선택하기 위함이다. 

이렇게 순회를 하는 도중, 다 뽑은 경우인 r=0과 r개를 다 뽑았지만 arr의 모든 원소를 다 검사했을 때인 target = n일 때이다. 후자의 경우 실패이므로 아무것도 하지 않고 return하게 된다. 

◎ 순열

순열은 순서가 있는 나열이다. 

우선 n개 중에 n개를 뽑는 순열을 보면 

void Swap(int arr[], int num1, int num2)
{
	int temp = arr[num1];
	arr[num1] = arr[num2];
	arr[num2] = temp;
}
void Permutation(int arr[], int index, int arr_size)
{
	// 탈출!
	if (arr_size - 1 == index)
	{
		for (int i = 0; i < arr_size; ++i)
		{
			cout << arr[i];
		}
		cout << endl;
		return;
	}

	for (int i = index; i < arr_size; ++i)
	{
		Swap(arr, index, i);
		Permutation(arr,index + 1, arr_size);
		Swap(arr, index, i);
	}
}


int main()
{
	int arr[5] = { 1,2,3,4,5 };
	Permutation(arr, 0, sizeof(arr) / sizeof(int));
}

(1,2,3,4,5) 의 배열에서 5개 중 5개를 뽑는 순열을 구하면 순열 공식에 의해 총 120개가 나오게 된다. 

arr배열 자체를 위에서 구한 조합을 이용해 정렬하는 것이다. 

먼저 swap을 이용해서 index번째의 자리 수가 1,2,3,4,일 때를 조사한다. index번째 자리를 선택한 후에 재귀를 통해 그 다음 자리를 선택하다가 arr의 마지막을 가리키면 끝이 난다.

재귀 후 다시 swap으로 바꿔준 값을 원상복구를 하면 다시 각 자리 수가 1일 때, 2일 때, 3일 때, 4일 때를 모두 조사할 수 있다. 

n개에서 n개를 뽑는 경우를 구했으니 이제 n개 중 r개를 뽑는 경우를 구하면 되는데 

이건 위에서 구한 조합을 이용하면 된다. 먼저 nCr을 이용해 n개 중에 r개를 뽑은 후에 r개의 수로 이루어진 숫자들을 permutation을 이용해서 정렬해주면 된다. 

void Swap(int arr[], int num1, int num2)
{
	int temp = arr[num1];
	arr[num1] = arr[num2];
	arr[num2] = temp;
}
void Permutation(int arr[], int index, int arr_size)
{
	// 탈출!
	if (arr_size - 1 == index)
	{
		for (int i = 0; i < arr_size; ++i)
		{
			cout << arr[i];
		}
		cout << endl;
		return;
	}

	for (int i = index; i < arr_size; ++i)
	{
		Swap(arr, index, i);
		Permutation(arr,index + 1, arr_size);
		Swap(arr, index, i);
	}
}
void Combination(int arr[], int n, int r, int index, int target, int comb_arr[])
{
	if (r == 0)
	{
		Permutation(comb_arr, 0, 3);
		cout << endl;
	}
	else if (target == n)
	{
		return;
	}
	else
	{
		comb_arr[index] = arr[target];
		Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); 
		Combination(arr, n, r, index, target + 1, comb_arr); 
	}
}

int main()
{
	int arr[5] = { 1,2,3,4,5 };

	int* comb_arr = new int[5];

	Combination(arr, 5, 3, 0,0 , comb_arr);
}

혹시 이 포스팅을 보시는 분께..

참고 자료;

it-earth.tistory.com/53

onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/

Permutation

순열

◎ 수학에서 순열 구하기

n개에서 r개를 택하는 순열이란 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것이다. 

여기서 중요한 것은 '순서 있게'다. 왜냐하면 개념이 헷갈리는 조합은 '순서'가 없이 나열하는 것이기 때문에 구분을 잘 해야 한다. 

표현은 주로 nPr로 한다. (n개에서 r개를 택하는 Permutation)

이 순열을 구하는 방법은 간단하다. 바로 팩토리얼을 이용하면 된다.

식을 간단하게 표현하면 위와 같다. 

◎ Permutation 사용

순열을 구하기 위해서는 재귀를 통해서 직접 구현할 수도 있다. 하지만 stl에 있는 기능을 가져다가 사용하면 빠르고 간단하게 순열을 만들 수 있다.

std::prev_permutation과 std::next_permutation은 현재 범위가 현재보다 더 작은 순열(이전 순열) 또는 더 큰 순열(다음순열)이 되도록 요소들을 정리한다. 이전 순열이나 다음 순열이 있으면 true, 없으면 false를 리턴한다. 

이때 순열이 끝나 false를 리턴하는 경우는 완전히 역순이 되는 경우다. 이 때 다시 원래 순서대로 바꾼뒤에 false를 리턴하는 것이다. 

ex) 1234의 경우 return 하기 직전 4321였다가 false를 리턴할때 다시 1234로 만들어준다. 

단 permutation은 중복이 있는 경우에는 중복을 제외하고 순열을 만들어준다. 

permutation 기능의 원리는 다음과 같다.

1. 우선 뒤에서부터 탐색을 시작한다. 오름차순의 형태를 띄는 구간이 나올 때까지 진행하며 작은 쪽은 i, 큰 쪽은 ii라고 가정한다. 

2. 그 다음에는 뒤에서부터 i보다 큰 j를 찾아 i와 j를 바꿔준다.

3. 그 후 ii를 포함해 뒷부분을 모두 reverse한다. 

범위를 이전 순열로 만드는 것

범위를 다음 순열로 만드는 것

위의 인자에 정렬 기준을 명시적으로 사용할 수 있다. 기본적으로는 std::less가 사용된다.

두 알고리즘 중 어떤 것을 사용하든, 주어진 범위의 모든 순열을 손쉽게 생성할 수 있다. 

ex ) permutation을 사용한 예시 

#include <algorithm>

std::vector<int> Init{1,2,3};
do{
	for(auto i:Init) std::cout << i;
	std::Cout << " ";
} while(std::next_permutation(Init.begin(), Init.end())); 

// 출력 예시 123 132 213 231 312 321 

std::reverse(Init.begin(), Init.end());
do{
	for(auto i:Init) std::cout << i;
    std::cout << " ";
 } while(std::prev_permutation(Init.begin(), Init.end()));
 
 // 출력 예시 321 312 231 213 132 123

permutation말고 직접 순열 구하기? 

참고 자료;

namu.wiki/w/%EC%88%9C%EC%97%B4

핵심 C++ 표준 라이브러리 (라이너 그림 지음; 류광 옮김. 인사이트) 

jeonggyun.tistory.com/110