[Algorithm, C++] next_permutation, prev_permutation과 순열, 조합

개요

이전 게시글에서 백트래킹 기법을 사용해 배열을 통해 순열과 조합을 구현했다. 다만, 백트래킹을 사용한 순열과 조합의 구현은 복잡하기 때문에 실수할 여지가 있다. 이번 게시글에서는 algorithm 헤더파일의 next_permutation과 prev_permutation을 통해 순열과 조합을 쉽게 구현하는 방법을 알아보자.

next_permutation로 순열 구하기

next_permutation

• bool std::next_permutation(BidirIt first, BidirIt last) // STL 컨테이너 사용 가능
• bool std::next_permutation(T *first, T *last) // 배열 사용 가능

[first, last) 범위에서 다음 수열 결과를 인수로 전달된 컨테이너 or 배열(이하 배열)에 저장한다.

다음 수열이 존재하면 true를 반환하고, 존재하지 않으면 false를 반환한다.

 

전달되는 배열은 반드시 오름차순으로 정렬되어있어야 한다.

또한, 중복 순열도 처리할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[4] = { 1, 2, 3, 4 }; // 반드시 오름차순으로 정렬된 상태여야 함

int main()
{
	do
	{
		for (int i = 0; i < 4; i++)
		{
			cout << arr[i] << " ";
		}
		cout << '\n';
	} while (next_permutation(arr, arr + 4)); // nPn과 같음 => O(n!)
}

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

prev_permutation로 순열 구하기

prev_permutation

• bool std::prev_permutation(BidirIt first, BidirIt last) // STL 컨테이너 사용 가능
• bool std::prev_permutation(T *first, T *last) // 배열 사용 가능

next_permutation 메서드와 기본적으로 비슷하지만 순열을 반대 순서로 구한다는 점이 다르다.

 

전달되는 배열은 반드시 내림차순으로 정렬되어있어야 한다.

또한, 중복 순열도 처리할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[4] = { 4, 3, 2, 1 }; // 반드시 내림차순으로 정렬된 상태여야 함

int main()
{
	do
	{
		for (int i = 0; i < 4; i++)
		{
			cout << arr[i] << " ";
		}
		cout << '\n';
	} while (prev_permutation(arr, arr + 4)); // nPn과 같음 => O(n!)
}

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

조합

조합은 next_permutation과 prev_permutation 둘 다 사용해 구현할 수 있다.

조합을 구현할 때는 기존 배열과 크기는 같고 0과 1로 이루어진 배열이 필요하다.

그리고 그 배열에 대해 permutation 메서드를 실행한 후, i번째 값이 1또는 0일때 출력하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[4] = { 1, 2, 3, 4 }; // 오름차순 정렬 배열
int tmp[4] = { 0, 0, 0, 1 }; // 4C3
// next_permutation은 tmp가 사전순으로 정렬이 되어있어야 하므로 nCr에서 r을 0으로 설정

int main()
{
	do
	{
		for (int i = 0; i < 4; i++)
		{
			if (tmp[i]==0) // 0인 것에 대해 출력해야 함
			{
				cout << arr[i] << " ";
			}			
		}
		cout << '\n';
	} while (next_permutation(tmp, tmp + 4));
}

#include <iostream>
#include <algorithm>
using namespace std;

int arr[4] = { 1, 2, 3, 4 }; // 정렬된 상태의 배열이어야 함
int tmp[4] = { 1, 1, 1, 0 }; // 4C3
// prev_permutation은 tmp가 사전역순으로 정렬이 되어있어야 하므로 nCr에서 r을 1으로 설정

int main()
{
	do
	{
		for (int i = 0; i < 4; i++)
		{
			if (tmp[i]) // 1인 것에 대해 출력해야 함
			{
				cout << arr[i] << " ";
			}
		}
		cout << '\n';
	} while (prev_permutation(tmp, tmp + 4));
}

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

백트래킹과 next_permutation, prev_permutation

• next_permutation, prev_permutation: 재귀함수를 구현하지 않아 편리하고 실수할 가능성이 적음
• 백트래킹: 다음 수열을 생성하지 않기 때문에 빠름

위의 특징에 의해 각각 다음과 같은 경우에 사용하는 것이 유리함

• 효율성을 고려하지 않고 단순히 순열, 조합을 구하는 경우 => next_permutation, prev_permutation
• 중복순열, 중복조합을 구하거나 시간 최적화가 필요한 경우 => 백트래킹