C++ STL(표준 템플릿 라이브러리)에서 제공하는 next_permutation 함수는 지정된 범위 [first, last] 내의 요소들을 사전순으로 다음에 오는 순열로 재배치하는 기능을 수행합니다. 여기서 순열(permutation)이란 N개의 원소가 가질 수 있는 N!가지 배열 조합 각각을 의미합니다. 이 글에서는 STL의 next_permutation을 활용해 모든 순열을 출력하는 C++ 프로그램을 소개합니다.
동작 원리 및 알고리즘
프로그램의 전체적인 흐름은 다음과 같습니다.
시작
정수형 배열 변수 elements[]를 선언한다.
사용자로부터 데이터 개수 e를 입력받는다.
키보드로 입력받은 e개의 데이터로 배열 elements[]를 초기화한다.
배열의 모든 원소를 오름차순으로 정렬한다.
do
show(elements, e) // 배열의 현재 상태를 출력
while (next_permutation(elements, elements + e))
종료next_permutation은 현재 순열보다 사전순으로 바로 다음 큰 순열로 배열을 변환하며, 더 이상 다음 순열이 존재하지 않으면 false를 반환합니다. 따라서 do-while 루프와 함께 사용하면 첫 번째 순열부터 마지막 순열까지 모든 경우를 순차적으로 출력할 수 있습니다. 주의할 점은 반드시 배열을 먼저 오름차순 정렬해야 가장 작은 순열부터 시작하여 전체 순열을 빠짐없이 얻을 수 있다는 것입니다.
예제 코드
#include<iostream>
#include <algorithm>
using namespace std;
void show(int a[], int n) {
for(int i = 0; i < n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
int main () {
int e, i;
cout<<"Enter number of elements to be inserted: ";
cin>>e;
int elements[e];
for (i = 0; i < e; i++) {
cout<<"Enter "<<i + 1<<" element: ";
cin>>elements[i];
}
sort (elements, elements + e);
cout << "The "<<e<<"! possible permutations with ";
cout<<e<<" elements: "<<endl;
do {
show(elements, e);
}
while (next_permutation(elements, elements + e));
return 0;
}코드 설명
- show 함수: 배열의 원소를 하나씩 공백으로 구분하여 화면에 출력하는 보조 함수입니다.
- 입력 처리: 사용자로부터 원소 개수 e를 받은 후, e개의 정수를 차례대로 배열에 저장합니다.
- sort 호출:
<algorithm>헤더의sort함수로 배열을 오름차순 정렬하여 순열 생성의 시작점을 만듭니다. - do-while 루프: 현재 배열 상태를 출력한 뒤
next_permutation으로 다음 순열을 생성하고, 더 이상 남은 순열이 없을 때까지 반복합니다.
실행 결과
4개의 원소(7, 6, 2, 10)를 입력했을 때의 실행 결과입니다. 총 4! = 24가지 순열이 사전순으로 출력됩니다.
Enter number of elements to be inserted: 4 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 2 Enter 4 element: 10 The 4! possible permutations with 4 elements: 2 6 7 10 2 6 10 7 2 7 6 10 2 7 10 6 2 10 6 7 2 10 7 6 6 2 7 10 6 2 10 7 6 7 2 10 6 7 10 2 6 10 2 7 6 10 7 2 7 2 6 10 7 2 10 6 7 6 2 10 7 6 10 2 7 10 2 6 7 10 6 2 10 2 6 7 10 2 7 6 10 6 2 7 10 6 7 2 10 7 2 6 10 7 6 2
마무리
next_permutation은 완전 탐색(brute force) 문제, 조합 최적화, 알고리즘 대회 등에서 매우 유용하게 활용되는 함수입니다. 시간 복잡도는 한 번의 호출당 O(N)이며, 전체 순열을 탐색할 경우 O(N × N!)이 소요됩니다. 원소 개수가 많아지면 순열의 수가 급격히 증가하므로, 실무에서는 N이 작은 경우(대략 10 이하)에 사용하는 것이 좋습니다. 또한 이전 순열을 구하고 싶다면 prev_permutation 함수를 동일한 방식으로 사용할 수 있습니다.