#pragma warning(disable:4996)

#include <cstdio>
#include <tchar.h>
#include <Windows.h>
#include <vector>
using namespace std;

/*
	submit time : 1
	request :
		Given a collection of numbers, return all possible permutations.

		For example,
		[1,2,3] have the following permutations:
		[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
*/

void Swap(int* data, int i, int j) {
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

void helpPermute(vector<vector<int> >& result, vector<int>& num, int length, int index) {
	if (index == length - 1)
		result.push_back(num);

	int vernier = index;
	while (vernier < length) {
		Swap(&num[0], index, vernier);
		helpPermute(result, num, length, index + 1);
		Swap(&num[0], index, vernier);
		++vernier;
	}
}

vector<vector<int> > permute(vector<int> &num) {
	vector<vector<int> > result;
	int length = num.size();
	if (length == 0) return result;

	helpPermute(result, num, length, 0);

	return result;
}

//===================Test====================
void printVec(vector<int>& vec) {
	vector<int>::iterator iter = vec.begin();
	for (; iter != vec.end(); ++iter)
		printf("%d ", *iter);
	printf("\n");
}

void Test(vector<int>& num) {
	vector<vector<int> > result = permute(num);
	vector<vector<int> >::iterator iter = result.begin();
	for (; iter != result.end(); ++iter)
		printVec(*iter);

	printf("\n");
}

void Test1() {
	int data[] = { 3, 7, 9, 13 };
	vector<int> num(data, data + sizeof(data) / sizeof(int));
	Test(num);
}

int _tmain(int arc, _TCHAR* argv[]) {
	Test1();

	system("pause");
	return 0;
}