#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

// Solution overview:
// Along with inputting the array of ints, an additional auxilary
// array (indices) is initialized: [0, 1, 2, ..., n-1].  The 
// make_next_perm function modifies this array to find the next 
// permutation in lexicographic order.  (So we're actually permuting
// the indices array.)  The indices array is then used to generate a 
// permutation of the original array.


// function headers:

// prompt user for permutation size; ensure it's at least 1
int prompt_size();

// given a permutation of size n, generates the next in lexicographic order
int make_next_perm( int p[], int n );

// computes the total numbers of permutations on n objects (no duplicates)
long numperms( int n );

int main()
{
  // get input from user
  const int array_size = prompt_size();
  int ints[array_size], indices[array_size];
  const int nump = numperms( array_size );

  cout << "Enter the ints, each separated by whitespace:" << endl;
  for(int i = 0 ; i < array_size; i++)
  {
    cin >> ints[i];
    indices[i] = i;
  }

  // find and diplay the permutations
  cout << "The permutations: " << endl;
  for( long i = 0; i < nump; i++ )
  {
    for( int j = 0; j < array_size; j++ )
      cout << ints[indices[j]] << " ";
    cout << endl;

    make_next_perm( indices, array_size );
  }

  return 0;
}

int make_next_perm( int b[], int n )
{
  // this function rearranges b (a perm. on n objects) so that it
  // becomes the next perm. in lexicographic order.  This algorithm
  // came from a "combinatorics algorithms" textbook...

  int i, temp;
  for(i = n-2; i>=0; i--)
    if(b[i]< b[i+1]) break;
  int j, min = n, mini = n-1;
  for(j = i + 1; j<n; j++)
  {
    if(b[j]<=min && b[j]>b[i])
    {
      min = b[j];
      mini = j;
    }
  }
  j = mini;
  temp = b[j];
  b[j] = b[i];
  b[i] = temp;
  int l = n-1;
  for(j=i+1; j<=(i+n)/2; j++)
  {
    temp = b[j];
    b[j] = b[l];
    b[l] = temp;
    l = l-1;
  }
  return 1;
}

// basically just computes and returns n! (assumes n>=0)
long numperms( int n )
{
  long ans = 1;
  for( int i = n; i > 0; i-- )
    ans *= i;
  return ans;
}

// 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;
}