순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
https://ko.wikipedia.org/wiki/순열
n개의 원소 중 r개를 뽑아 만드는 permutation
(r <= n, 0! = 1) // 중요 조건
기본 : (n-0)*(n-1)*(n-2)...*(n-r+1)
중복순열 : n * n * n ... n = n^r
#include <string>
#include <vector>
#include <iostream>
using namespace std;
template<typename T>
void Swap(T & a, T & b)
{
T temp = a;
a = b;
b = temp;
}
template<typename T>
void Permutation(vector<T> &data, vector< vector<T> > &result, const int &n, const int &r, int depth)
{
if (depth == r) // escape condition
{
vector<T> resultElement(data.begin(), data.begin()+r);
result.push_back(resultElement);
return;
}
for(int i = depth; i < n; i++)
{
swap(data[i], data[depth]);
Permutation<T>(data, result, n, r, depth + 1);
swap(data[i], data[depth]);
}
}
template<typename T>
vector< vector<T> > CreatePermuation(vector<T> &data, int &n, int &r){
vector< vector<T> > rs;
Permutation(data, rs, n, r, 0);
return rs;
}