#include <vector>
#include <iostream>

using namespace std;

vector<int> insert(const vector<int> & prev, int pos, int elem){
	vector<int> v;
	
	for (int i=0; i<pos; i++)
		v.push_back(prev[i]);
	v.push_back(elem);
	for (int i=pos; i<prev.size();i++)
		v.push_back(prev[i]);

	return v;
}

vector<vector<int> > getPermutationssOfOneToN(int n){
	vector<vector<int> > v;
	vector<int> s;
	if (n<=0){
		v.push_back(s);
		return v;
	}
	else{
		vector<vector<int> > v2 = getPermutationssOfOneToN(n-1); // all permutations of {1 .. n-1}
		for (int i=0; i<v2.size(); i++){
			s = v[i]; // s is one permutation of {1 ... n-1}
			for (int j=0; j<=s.size(); j++){
				vector<int> new_perm = insert(s,j,n);
				v.push_back(new_perm);
			}
		}
		return v;
	}
}

void print_vector(const vector<int>& v){
	for (int i=0; i<v.size(); i++)
		cout << v[i] << " ";
	cout << endl;
}

int main(){
	for (int i= 1; i<5; i++){
		cout << "permutationss of {1.." << i << "}:" << endl;
		vector<vector<int> > perms = getPermutationssOfOneToN(i);
		for (vector<vector<int> >::iterator itr=perms.begin(); itr<perms.end(); itr++)
			print_vector(*itr);
	}

}