#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:
// Unlike the previous version of this problem, this version assumes
// that the input array may contain duplicates.

// Solution overview:
// This solution generates permutations the same way that the old
// version did, except now we add each new permutation to a list of
// permutations.  If we generate a duplicate, we simply skip that one.
// We wait to output the permutations until all have been generated.

// Disclaimer: see comments above check_perm_list function
// implementation regarding C++ 2-D arrays...

// 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
void make_next_perm( int p[], int n );

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

// examine the list of permutations thus far (perm_array - a 2-D array)
// to see if our current permuatation candidate is really a duplicate
int check_perm_list( int perm[], int i,
                     int* perm_array, int m, int n );

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

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

  // find the permutations (permute the 'indices' array)
  int array_of_perms[nump][perm_len];
  int temp_perm[perm_len];
  int actual_current_perm = 0;
  for( int i = 0; i < nump; i++ )
  {
    if ( i>0 )
      make_next_perm( indices, perm_len );

    // make next permutation candidate
    for( int j = 0; j < perm_len; j++ )
      temp_perm[j] = the_ints[indices[j]];

    // conditionally add the permutation to our list of permutations
    if( check_perm_list( temp_perm, actual_current_perm,
                         &array_of_perms[0][0], nump, perm_len ) )
    {
      for( int k = 0; k < perm_len; k++ )
        array_of_perms[actual_current_perm][k] = temp_perm[k];
      actual_current_perm++;
    }
  }

  // display the permutations
  cout << "The permutations: " << endl;
  for( int i = 0; i < actual_current_perm; i++ )
  {
    for( int j = 0; j < perm_len; j++ )
      cout << array_of_perms[i][j] << " ";
    cout << endl;
  }

  return 0;
}


// examines the list of permutations thus far (perm_array) to see if
// our current permuatation candidate (perm) is really a duplicate

// inputs:
// i is how many permutations in perm_array to check (i.e. how many
// rows through which to iterate); m & n are the dimensions
// (rows & cols, respectively) of perm_array (thus, n is also the
// number of elements in perm)

// output:
// returns 0 if perm was found in perm_array, 1 if not

// additional comments:
// Using two-dimensional arrays in C++ as this solution does is not
// generally advisable; using a vector or some other pre-defined 2-D
// matrix class (e.g. apmatrix), or writing our own data structure 
// to do this would be a better idea...
// Another disadvantage of this implementation is that it declares a 2-D 
// array that is potentially much larger than necessary to hold all the
// permutations (if there are lots of duplicates).

int check_perm_list( int perm[], int i,
                     int* perm_array, int m, int n )
{
  for( int j = 0; j < i; j++ )
  {
    int duplicate_found = 1;

    for( int k = 0; k < n; k++ )
      if( perm[k] != perm_array[j*n+k] ) // jth row, kth col
        duplicate_found = 0;  // not a match, check next perm

    if( duplicate_found )
      return 0; // found a duplicate, return false
  }
  return 1; // went all way through list, didn't find duplicate
}


// rearranges b (a permutation of the ints 0, 1, ..., n-1) so that
// it becomes the next perm. in lexicographic order.  This algorithm
// comes from a "combinatorics algorithms" textbook...

void make_next_perm( int b[], int n )
{
  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;
  }
}

// basically just computes and returns n!
// assumes n is nonnegative (would just return 1 if not...)
int numperms( int n )
{
  int 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;
}