[CPP STL] next_permutation

next_permutation을 이용한 순열

사전순 (1-2-3-4)의 순열을 구하고 싶다면 next_permutation
역사전순 (4-3-2-1)의 순열을 구하고 싶다면 prev_permutation

#include <iostream>
#include <vector>
#include <algorithm> // 해당 헤더로 next_permutation을 이용할 수 있다.

using namespace std;

int arr[4]; // 1~4까지 들어갈 배열
vector<int> v(4); // 벡터도 가능

int main() {


	// 1부터 4까지 배열과 벡터에 저장
	for (int i = 0; i < 4; i++) {
		v[i] = i + 1;
		arr[i] = i + 1;
	}

	// next_permutation을 통해서 다음 순열 구하기
	
	do { // 배열

		for (int i = 0; i < 4; i++) {
			cout << arr[i] << " ";
		}

		cout << '\n';

	} while (next_permutation(arr, arr+4));
	
    
	cout << "----------------------------------------------\n";
    
    do { // 벡터

		for (int i = 0; i < 4; i++) {
			cout << v[i] << " ";
		}

		cout << '\n';

	} while (next_permutation(v.begin(), v.end()));
	return 0;
    
    /*
    1 2 3 4
    1 2 4 3
    1 3 2 4
    1 3 4 2
    1 4 2 3
    1 4 3 2
    2 1 3 4
    2 1 4 3
    2 3 1 4
    2 3 4 1
    2 4 1 3
    2 4 3 1
    3 1 2 4
    3 1 4 2
    3 2 1 4
    3 2 4 1
    3 4 1 2
    3 4 2 1
    4 1 2 3
    4 1 3 2
    4 2 1 3
    4 2 3 1
    4 3 1 2
    4 3 2 1
    */

}

---

next_permutation을 이용한 조합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> s{ 1, 2, 3, 4 };
    vector<int> temp{ 1, 1, 0, 0 };
 
    do {
        for (int i = 0; i < s.size(); ++i) {
            if (temp[i] == 1)
                cout << s[i] << ' ';
        }
        cout << endl;
    } while (prev_permutation(temp.begin(), temp.end()));
}


/*
1 2
1 3
1 4
2 3
2 4
3 4
*/

이때 next_permutaion을 사용하면 오름차순으로 정렬되기 때문에, 조합은 내림차순으로 출력된다. 하지만 prev_permutation을 쓰면 모든 조합의 경우의 수를 오름차순으로 출력한다.

next_permutation 함수 뜯어보기

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (true) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

1. 맨 뒤에서부터 인접한 두개의 수를 비교한다. (뒤에서부터 내림차순이 아닌 위치를 찾기 위함)
2. 앞의 수(A)가 작을 경우 비교를 멈춘다. (A 뒤에 있는 수들은 내림차순으로 정렬되어있는 상태)
3. 맨 뒤에서부터 A와 비교하여 A보다 커지는 지점(B)을 찾는다.
4. A와 B를 스왑한다. (여전히 뒤의 수들은 내림차순)
5. 뒤의 수들을 반전시킨다. (내림차순에서 오름차순으로 만든다.)

---

🍏 출처

https://blog.uniony.me/cpp/next_permutation/
https://mjmjmj98.tistory.com/38