[알고리즘] 탐색(2) - 순열(Permutation)

 개념 

서로 다른 n개의 수 중에 r개를 선택하여 나열
nPr = n x n-1 x n-2 ...... x n-r+1

 

리스트를 순서대로 수를 뽑아 나열하는 것. 즉, 순서에 의미가 있는 것이 순열입니다. 반대로 순서에 의미가 없다면 조합이 되겠습니다. 

 

• Itreative function
• Recursive function

 

Itreative function은 c++의 STL인 next_permutation 방식입니다. 설명과 직접 구현을 해보도록 하겠습니다.

Recursive function은 재귀 호출 방식입니다. 마찬가지로 직접 구현 해보도록 하겠습니다.

 

 

 

 Iterative function (next_permutation) 

① 뒤쪽부터 탐색하며 꼭대기를 찾자

 

꼭대기를 왜 찾아야 할까요? 두 가지 리스트를 가지고 비교를 해보겠습니다.

 

[ 1 3 5 4 2 ]

[ 5 4 3 2 1 ]

 

순열의 마지막 순서

꼭대기 찾기

 

눈치 채셨나요? 5 4 3 2 1은 순열의 마지막 순서입니다. 왜 꼭대기를 찾을까요? 순열의 순서를 결정하기 위해서입니다.

 

순서를 결정하기 위해서는 꼭대기에서 왼쪽으로 내려오는 원소가 있는지 파악해야합니다. 이제 편의상 꼭대기를 i라고 하겠습니다. 

 

• i - 1 : 교환 자리
• if (i == 0) : 가장 큰 순열

 

 

② i - 1 위치의 값과 교환할 값 찾기

 

next_permutation, 즉 다음 순서의 순열을 찾는 과정이기 때문에 현재 단계의 순열보다 다음 단계의 순열의 값이 커야합니다. 이말을 그대로 받아들이면 i-1위치의 값과 교환할 값은 가장 뒤에서 부터 탐색해서 i-1위치의 값보다 커지는 순간의 값입니다.

 

j 찾기

 

j는 항상 존재한다는것을 알 수있습니다. 이유는 i-1 < i 라는 것은 1번을 통해 밝혀졌습니다. 따라서 맨뒤의 원소가 i라고 해도 j의 위치는 i가 되고 따라서 i-1 < j가 됩니다.

 

 

③ i-1 위치의 값과 j 위치의 값 교환하기

④ i ~ 마지막까지의 값들을 정렬하기

 

[1 4 5 3 2] -> [1 4 2 3 5]

 

기존의 값 [1 3 5 4 2]에서 다음 순열의 순서는 [1 4 2 3 5]가 됩니다. 즉 교환한 값 기준으로 정렬 기준이 반대로 되어야합니다. 현재 i ~ 마지막 [5 3 2]는 내림차순으로 정렬되어 있기 때문에 간단한 swap으로 오름차순으로 정렬할 수 있습니다.

 

 

 

⑤  ① ~ ④ 반복하기

 

 

 구현 

template <typename T>
__inline void SWAP(T& a, T& b) { T t = a; a = b; b = t; }

template <typename T>
bool nextPermutation(vector<T>& data)
{
	int i = data.size() - 1, j = data.size() - 1;

	/* 1번 : 꼭대기 찾기 */
	while (i > 0 && data[i - 1] >= data[i]) i--;
	if (i == 0) return false;

	/* 2번 j값 찾기 */
	while (data[i - 1] >= data[j]) j--;
	SWAP(data[i - 1], data[j]);		// 3번 스왑하기

	/* 4번 나머지 정렬하기 */
	j = data.size() - 1;
	for (; i < j; ++i, --j)
		SWAP(data[i], data[j]);
	return true;
}

/* 호출 방법 */
do {
	for (int a : arr)
		cout << a << " ";
	cout << '\n';
} while (nextPermutation(arr));

 

do - while을 사용하는 이유는 처음 순열 순서를 보존하기 위해서입니다.

 

next_permutation을 직접 구현을 해보았는데, 사실 c++을 사용한다면 제공해주는 라이브러리를 이용하면됩니다. 파라미터로 순열의 순서를 구하고자하는 범위를 iterator를 통해 전달하면 됩니다. 또한 prev_permutation도 제공을 하고 있습니다. 

 

do {
	for (int a : arr)
		cout << a << " ";
	cout << '\n';
} while (next_permutation(arr, arr + n); // or prev_permutation(arr,arr+n)

 

 

 

 Recursive function 

재귀 호출을 이용해서 순열을 구성하기 위해서는 세가지 파라미터가 필요합니다.

 

• nPr에서 n
• nPr에서 r
• 기저 조건을 위한 idx

 

그러나 n과 r이 고정되어 있다면 idx하나만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 3가지가 필요합니다.

 

• 방문여부를 체크할 bool형 배열
• 나열한 수를 담을 배열
• 나열되어져야 할 수를 담은 배열

 

어떤 수를 담았을 경우 중복해서 담게되면 중복순열이 되기때문에 방문여부를 체크할 배열이 필요합니다.

 

 구현 

// 순열 : nPr
void RecursivePermutation(int idx, int n, int r)
{
	// base condition
	if (idx == r)
	{
		for (int i = 0; i < r; ++i)
			cout << ans[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (visited[i]) continue;
		ans[idx] = arr[i];
		visited[i] = true;
		RecursivePermutation(idx + 1, n, r);
		visited[i] = false;
	}
}

RecursivePermutation(0,5,3) // 5P3

 

for문을 0번부터 n번까지 순회하면서 방문하지않은 곳을 체크해 ans배열에 넣습니다. 만약 방문체크를 하지 않는다면 중복순열이 되겠죠?

 

idx가 r이되는 순간 r개의 수가 뽑혔다는 뜻이므로 return하게 됩니다. 그리고 재귀 호출하는 안밖으로 visited의 상태를 되돌리는데, 이유는 이 후에 포스팅할 퇴각검색(backtracking)과 DFS(Depth-First-Search)와 연관이 있습니다. 

 

한번 생각해보고 넘어갈 것은 방문처리입니다. 비트 마스크를 통해 방문여부를 처리 할 수 도 있습니다.

 

// 순열 : nPr
void RecursivePermutation(int idx, int n, int r, int flag)
{
	// base condition
	if (idx == r)
	{
		for (int i = 0; i < r; ++i)
			cout << ans[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (flag & (1 << i)) continue;
		ans[idx] = arr[i];
		RecursivePermutation(idx + 1, n, r, flag | (1 << i));
	}
}

RecursivePermutation(0,5,3,0) // 5P3

 

flag를 원래 상태로 되돌려주기 위해 flag ^= (1 << i) 를 이용해도 되지만, 위와 같이 그저 | 연산을 이용해서 다음 재귀 호출할때만 값을 넘겨주도록 할 수도 있습니다.

 

주의할 점은  int형 변수는 비트를 최대 32bit를 이용할 수 있다는점을 간과해서는 안됩니다.

 

 시간복잡도 

순열은 어떻게 해도 시간복잡도는 O(n!)입니다.  nPr이기 때문이죠. 다만,  recursive function 사용시 호출되는 시간이 있기 때문에 next_permutation으로 사용한다면 어느정도 시간 단축은 가능합니다.

 

 정리 

리스트 11개 순열

리스트의 사이즈가 11인 전체 순열의 속도가 다음과 같이 나왔습니다. 

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

- ram : 8G