[C++] 순열 (Permutation) 구할 수 있는 알고리즘

개념

n개의 값 중에서 r개의 숫자의 순서를 고려해 나열한 경우의 수

 

nPr = n x n-1 x n-2 ...... x n-r+1
EX) {1,2,3} 총 3개의 값 중에서 3개의 숫자를 순서를 고려해 나열하면
1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1 로 총 6개 로 나타낼 수 있다 (3! = 1x2x3)

swap 방식

 

1. 0번째 인덱스 원소를 0번째 부터 n-1번째까지 위치를 바꾼다 (ABC, BAC, CBA)
2. 1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를 1번째부터 n-1번째까지 위치를 바꾼다
3. 이러한 과정을 n-1번 반복한다

 

순열들의 순서가 보장되지 않는다 EX) C,A,B가 먼저 나오는게 아니라 C,B,A가 먼저 노출됨

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

using namespace std;
vector<int> arr;
int n;

void Perm(int depth = 0, int k = 2)
{
	if (depth == k) 
	{
		for (int i = 0; i < n; i++)
			cout << arr[i] << ' ';

		cout << endl;
		return;
	}
	for (int i = depth; i < n; i++) 
	{
		swap(arr[i], arr[depth]); // 배열을 depth 에 따라 변경 
		Perm(depth + 1, k); 	  // 재귀 함수 
		swap(arr[i], arr[depth]); // 변경된 배열을 다시 원복
	}
}

int main() 
{
	arr = { 1,2,3 };
    n = arr.size();
	Perm();
	return 0;
}

백트래킹 방식

1. DFS를 돌면서 모든 인덱스에 방문해 output 배열에 값을 넣는다
2. 이미 들어간 값은 visited 를 true 로 변경해서 중복해서 값이 들어가지 않도록 한다
3. 이러한 과정을 depth 가 r 값과 같아질 때까지 반복한다

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

using namespace std;
vector<int> arr, p;
vector<bool> vis;
const int k = 3;
int n;

void Perm(int depth = 0)
{
	if (depth == k) 
	{
		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';

		cout << endl;
		return;
	}
	for (int i = 0; i < n; i++) 
	{
		if (!vis[i])
		{
			vis[i] = true;
			p[depth] = i + 1;
			Perm(depth + 1);
			vis[i] = false;
		}
	}
}

int main() 
{
	arr = { 1,2,3 };
	n = arr.size();
	vis.resize(n);
	p.resize(n);
	Perm();
	return 0;
}

 

시간 복잡도) O(n!) nPr이기 때문

 

출처