[C++] 순열 / 조합 구하기 (next_permutation/prev_permutation 함수)

순열

next_permutation

C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있다.

기본은 오름차순이다, 즉 내림차순인 prev_permutation을 사용하기 위해서는 내림차순으로 정렬 되어있어야 한다.

중복이 있는 원소들은 제외하고 순열을 만들어준다.

// default
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
 
// custom
bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

next_permutation

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
	vector<int> v{ 1, 2, 3 };
	sort(v.begin(), v.end());

	auto s = v.begin(), e = v.end();

	while (next_permutation(s, e))
	{
		for (auto iter = s; iter != e; iter++)
			cout << *iter << ' ';

		cout << endl;
	}
	return 0;
}

prev_permutation

// default
bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
 
// custom
bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
	vector<int> v{ 1, 2, 3 };
	sort(v.begin(), v.end(), greater<int>());

	auto s = v.begin(), e = v.end();

	while (prev_permutation(s, e))
	{
		for (auto iter = s; iter != e; iter++)
			cout << *iter << ' ';

		cout << endl;
	}
	return 0;
}

조합

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

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	vector<bool> tmp{ 1, 1, 0, 0 };	
	auto s = tmp.begin(), e = tmp.end();

	do
	{
		for (int i = 0; i < v.size(); i++)
		{
			if (tmp[i])
				cout << v[i] << ' ';
		}
		cout << endl;
	} while (prev_permutation(s, e));
	return 0;
}