permutation with literation in C++

 Most examples on the internet to implement permutation are based on RECURSION. Personally I think every thing based on recursion can also be done with iteration. The basic idea behind for those two ways are the same, finding the relation between X(k) and X(k+1).

#include <iostream>

#include <vector>

using namespace std;

typedef vector<int> vi;

typedef vector<vector<int>> vvi;

void print_vvi(const vvi& ps)

{

for(auto p : ps){

for(auto e : p){

cout << e << " ";

}

cout << "\n";

}

}

vvi permute(int a[], int n, int k)

{

vvi ps0;

for(int i=0; i<n; i++){

vi p;

p.push_back(a[i]);

ps0.push_back(p);

}

if(k==1){

return ps0;

}

vvi pre_ps = ps0;

vvi ps;

for(int i=1; i<k; i++){

ps.clear();

for(int i=0; i<n; i++){

for(auto _p : pre_ps){

bool dup = false;

for(auto e : _p){

if(a[i] == e){

dup = true;

break;

}

}

if(!dup){

vi p = _p;

p.push_back(a[i]);

ps.push_back(p);

}

}

}

pre_ps = ps;

}

return ps;

}

int main()

{

int a[] = {1,2,3};

vvi ps = permute(a, sizeof(a)/sizeof(a[0]), 3);

print_vvi(ps);

return 0;

}