// random number generator; generates random permutations
// maximum length of permutation is 10000

#include<iostream.h>
#include <time.h>
#include<stdlib.h>

#define maxSize 10000
#define NumberPermutations 20

template<class T>
bool SSearch(T a[], const T& x, int n)
{// Search the unordered list a[0:n-1] for x.
 // Return true if found; return false otherwise.
   int i;
   for (i = 0; i < n && a[i] != x; i++);
   if (i == n) return false;
   return true;
}

template<class T>
void InsertionSort(T a[], int n)
{// Sort a[0:n-1].
   for (int i = 1; i < n; i++) {
      // insert a[i] into a[0:i-1]
      T t = a[i];
      int j;
      for (j = i-1; j >= 0 && t < a[j]; j--)
         a[j+1] = a[j];
      a[j+1] = t;
      }
}


int* randomPermutation(int Size)
{// generate a random permutation of 0, 1, 2, ......, Size-1
    int a[maxSize], i, tempNext;
    bool found = true;

    for(i=0; i<Size; i++) a[i] = -1;
    a[0] = random(Size);  // first random number; not a repeat
    for(i=1; i<Size; i++)
    {
        while(found)    //tempNext generated earlier
        {
            tempNext = random(Size); // next random number; possible repeat
            found = SSearch(a, tempNext, i);
        }
        found = true;
        a[i] = tempNext;
    }
    return a;   // suspicious pointer conversion
}               // to solve this problem, declare array a outside evrey block

void main( )
{
    int *A;
    int length;
    cout << "enter the length of permutations:  ";
    cin >> length;
    cout << "generate " << NumberPermutations << " permutations" << endl;
    cout << endl;
    randomize();
    for (int i=0; i<NumberPermutations; i++)
    {
        A = randomPermutation(length);
// **call insertion sort and measure sorting time for A[0:length-1]
// **compute average sorting time
        for (int j=0; j<length; j++) // **print permutations; delete this line
            cout << A[j] << " ";     // **delete this line
        cout << endl;                // **delete this line
    }
    getchar();
}