[C++] Permutation

• Rotate example: [ 1 2 3 4]-> 4 1 2 3 (right shift)
• Permutation of 1 2 3 4: [] = rotate, () = recursion
  • [1] => 1 (2 3 4)
  • [1 2] => 2 (1 3 4)
  • [1 2 3] => 3 (1 2 4)
  • [1 2 3 4] => 4 (1 2 3)
    
    
• Code

#include<iostream>
#include<vector>
using namespace std;

int count = 0;

void rotate(vector<int> &list, int x, int y) {
    int tmp = list[y];
    for (int i = y; i > x; i--) {
        list[i] = list[i-1];
    }
    list[x] = tmp;
}

void perm(int a, int n, vector<int> list){
    if (a < n){
        for (int i = a; i < n; i++) {
            vector<int> tmplist(list);
            rotate(tmplist, a, i);
            perm(a+1, n, tmplist);
        }
    }
    else{
        for (int i = 0; i < n; i++) {
            cout<<list[i]<<" ";
        }
        cout<<endl;
        count++;
    }
}

int main()
{
    int n;
    vector<int> list;
    cin>>n;
    list.resize(n);
    for (int i = 0;i < n; i++) {
        cin>>list[i];
    }
    perm(0, n, list);
    cout<<"count="<<count<<endl;
    return 0;
}