/*****************************************************************************
 * This program provides a more elaborate recursion example. The 'permutations'
 * function called on a vector of ints with the v_size argument 0 will display
 * all permutations of the elements of the vector. If the elements of the 
 * vector are distinct, each permutation will appear exactly once. 
 *
 *  The ability to generate all permutations of a collection of values is 
 *  useful for finding an order that is optimal relative to some objective.
 *  It is also used in statistical analyses.
 *
 * The function template for vector display is a preview of material in chapter
 * 8. To determine its function in this context, just replace all instances 
 * of the type 'T' with 'int'.
 ******************************************************************************/

#include<iostream>
#include<stdexcept>
#include<vector>
#include<algorithm>
using std::cout; using std::cin; using std::endl;
using std::domain_error; using std::vector;
using std::swap;
typedef vector<int>::size_type v_size;

/* This displays the elements a of vector separated by spaces. */
 template <class T>
 void show(const vector<T>& v)
{
	typedef typename vector<T>::size_type v_size;
	for(v_size i=0; i<v.size(); i++)
		cout<<v[i]<<" ";
}
/* 'permutations' outputs all permutations of the vector v in which only the
 * elements with indices between i and the v.size() are reordered.
 */
void permutations(vector<int> v, v_size i)
{
	/* base case- there is only one element in the range to be permuted,
	 * thus no action is necessary beyond displaying v.
	 */ 
	if(i==v.size()-1)
	{
		cout<<"(";
		show(v);
		cout<<") "<<endl;
		return;
	}
	/* Obtain the permutations affecting i through v.size() by 
	 * swapping each element with indices in that range into position i,
	 * then permuting the elements in positons i+1 through v.size().
	 */
	else
		for(v_size j=i;j!=v.size();j++)
		{
			swap(v[i],v[j]);
			permutations(v, i+1);
		}
					
			
}
/* 'permute' is a driver for the recursive 'permutations' that doesn't
 * require the user programmer to supply the 0.
 */

void permute(vector<int> v)
{
	permutations(v,0);
	return;
}
	

int main()
{
	vector<int> vec;
	/* Load a vector with the integers between 1 and 4. */
	for(int i=1; i!=5; i++)
		vec.push_back(i);

	permute(vec);
	return 0;
}