#include <iostream.h>

// Permutations Programming Problem
// Input: An array size, followed by the specified number of integers
// Output: Each possible permutation of the input array of ints

// Assumpution:
// The input array contains no duplicate ints

// Implementation note:
// This solution generates permutations recursively.

// A nonrecursive solution is available at the contest website:
// http://cs.wcu.edu/cscontest

// function headers:
int prompt_size();
void swap( int a[], int i, int j );
void perm( int list[], int k, int m );

int main()
{
  // get input from user:
  const int perm_len = prompt_size();
  int the_ints[perm_len];

  cout << "Enter the ints, each on a separate line:" << endl;
  for(int i = 0 ; i < perm_len; i++)
    cin >> the_ints[i];

  // find & display the permutations
  cout << "The permutations: " << endl;
  perm( the_ints, 0, perm_len-1 );

  return 0;
}


// recursively find and display permutations
void perm( int list[], int k, int m )
{
  if ( k==m )
  {
    // list has one permutation, output it
    for( int i = 0; i <= m; i++ )
      cout << list[i] << " ";
    cout << endl;
  }
  else
  {
    // list[k:m] has more than one permutation
    // generate these recursively
    for( int i = k; i <= m; i++ )
    {
      swap( list, i, k );
      perm( list, k+1, m );
      swap( list, i, k );
    }
  }
}

// prompt user for permutation size; ensure it's at least 1
int prompt_size()
{
  int p = 0;
  cout << "Enter number of integers in original array : ";
  cin >> p;
  while( p < 1 )
  {
    cout << "Please enter an array size of at least 1: ";
    cin >> p;
  }
  return p;
}

// swap a[i] and a[j]
void swap( int a[], int i, int j )
{
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}