[C++] Permutation(순열)

C++에서는 STL에서 순열을 지원한다.

nPr = n!/(n-r)! 로 경우의 수를 찾는 연산이다.

C++에서는 next_permutation과 prev_permutation을 사용하여 순열을 표현한다.

next_permutation : 오름차순의 배열을 기반으로 순열을 만든다.

prev_permutation : 내림차순의 배열을 기반으로 순열을 만든다.

#include<stdio.h>
#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;
void printV(vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << endl;
}
int main()
{
	vector <int> v;
	for (int i = 1; i <= 3; i++) {
		v.push_back(i);
	}
	do {
		printV(v);

	} while (next_permutation(v.begin(), v.end())); // 오름차순인 배열을 순열로 출력
	
	vector<int>v1;
	cout << "===================" << endl;
	for (int i = 3; i >= 1; i--) {
		v1.push_back(i);
	}
	do {
		printV(v1);

	} while (prev_permutation(v1.begin(), v1.end())); // 내림차순인 배열을 순열로 출력

}

배열의 종점인 end()를 넣지말고 대신 다른 것을 넣을 수 있다.

#include<stdio.h>
#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;
void printV(vector<int>& v) {
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << endl;
}

int main()
{
	vector <int> v;
	for (int i = 1; i <= 3; i++) {
		v.push_back(i);
	}
	do {
		printV(v);

	} while (next_permutation(v.begin(), v.begin() + 2)); // 오름차순인 배열을 순열로 출력
	// 배열의 0, 1 만의 순서를 고치게 된다. (v.being() ~ v.begin()+2)라는 범위를 만든것
	

}

 

배열의 종점인 end()대신 v.begin()+2를 넣어서 범위를 좁혀 내가원하는 순열의 종착지점을 정할 수 있다.

 

vector가 아닌 일반 배열에서의 사용

int main() {
	int arr[3] = { 2,3,1 };
	
	sort(arr, arr + 3);
	do {
		for (int i = 0; i < 3; i++) {
			cout << arr[i] << ' ';
		}
		cout << endl;
	} while (next_permutation(arr, arr+3));
	
	
}

일반 배열 순열