순열(Permutation)?

정의

순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.

참조

https://ko.wikipedia.org/wiki/순열

nPr

n개의 원소 중 r개를 뽑아 만드는 permutation 
(r <= n, 0! = 1) // 중요 조건

nPr에 대한 모든 경우의 수

기본 : (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;
    }