#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef unsigned long long int Lint;

typedef struct {
   Lint cnt;
   int **seq;
} seq;

typedef struct _node {
   int key;
   struct _node *L, *R;
} tnode;

int *genlist ( int n )
{
   int *A, i, j, t;

   A = (int *)malloc(n * sizeof(int));
   A[0] = 100 + rand() % 500;
   for (i=1; i<n; ++i) A[i] = A[i-1] + 1 + rand() % 50;
   for (i=1; i<n; ++i) {
      j = rand() % (i+1);
      if (j != i) {
         t = A[i]; A[i] = A[j]; A[j] = t;
      }
   }
   for (i=0; i<n; ++i) printf("%-5d", A[i]);
   printf("\n");
   return A;
}

Lint binomial ( int n, int r )
{
   double prod;

   prod = 1;
   while (r) {
      prod *= (double)n / (double)r;
      --n; --r;
   }
   return (Lint)round(prod);
}

Lint countseq ( int *A, int n )
{
   int *B, *C, i, l, r;
   Lint nl, nr;

   if (n <= 2) return 1;

   B = (int *)malloc((n-1)*sizeof(int));
   C = (int *)malloc((n-1)*sizeof(int));
   l = r = 0;
   for (i=1; i<n; ++i) {
      if (A[i] < A[0]) B[l++] = A[i];
      else C[r++] = A[i];
   }
   nl = countseq(B,l); free(B);
   nr = countseq(C,r); free(C);
   return nl * nr * binomial(l+r,l);
}

seq findallseq ( int *A, int n )
{
   int *B, *C, i, j, k, l, r, s, t, n1;
   Lint w;
   seq S, U, V;

   if (n <= 2) {
      S.cnt = 1;
      S.seq = (int **)malloc(sizeof(int *));
      S.seq[0] = (int *)malloc(2 * sizeof(int));
      for (i=0; i<n; ++i) S.seq[0][i] = A[i];
      return S;
   }

   B = (int *)malloc((n-1)*sizeof(int));
   C = (int *)malloc((n-1)*sizeof(int));
   l = r = 0;
   for (i=1; i<n; ++i) {
      if (A[i] < A[0]) B[l++] = A[i];
      else C[r++] = A[i];
   }
   U = findallseq(B,l); free(B);
   V = findallseq(C,r); free(C);
   S.cnt = (U.cnt) * (V.cnt) * binomial(l+r,l);
   S.seq = (int **)malloc(S.cnt * sizeof(int *));
   for (i=0; i<S.cnt; ++i) S.seq[i] = (int *)malloc(n * sizeof(int));
   s = 0;
   for (j=0; j<U.cnt; ++j) {
      for (k=0; k<V.cnt; ++k) {
         for (w=0; w<(1ULL<<(n-1)); ++w) {
            n1 = 0;
            for (t=0; t<n-1; ++t) {
               if (w & (1ULL << t)) ++n1;
            }
            if (n1 == r) {
               S.seq[s][0] = A[0];
               l = r = 0;
               for (t=0; t<n-1; ++t) {
                  S.seq[s][t+1] = (w & (1ULL << t)) ? V.seq[k][r++] : U.seq[j][l++];
               }
               ++s;
            }
         }
      }
   }
   for (i=0; i<U.cnt; ++i) free(U.seq[i]);
   for (i=0; i<V.cnt; ++i) free(V.seq[i]);
   free(U.seq); free(V.seq);
   return S;
}

void prnallseq ( seq S, int n )
{
   Lint i;
   int j;

   for (i=0; i<S.cnt; ++i) {
      printf("    Sequence %-5Lu : ", i+1);
      for (j=0; j<n; ++j) printf("%-5d", S.seq[i][j]);
      printf("\n");
   }
}

tnode *BSTins ( tnode *T, int x )
{
   tnode *p, *q;

   q = NULL; p = T;
   while (p) {
      if (x == p -> key) return T;
      q = p;
      p = (x < p -> key) ? p -> L : p -> R;
   }
   p = (tnode *)malloc(sizeof(tnode));
   p -> key = x;
   p -> L = p -> R = NULL;
   if (q == NULL) return p;
   if (x < q -> key) q -> L = p; else q -> R = p;
   return T;
}

tnode *BSTcons ( int *A, int n )
{
   int i;
   tnode *T;

   T = NULL;
   for (i=0; i<n; ++i) T = BSTins(T,A[i]);
   return T;
}

void preorder ( tnode *T )
{
   if (T == NULL) return;
   printf("%-5d", T-> key);
   preorder(T->L);
   preorder(T->R);
}

void inorder ( tnode *T )
{
   if (T == NULL) return;
   inorder(T->L);
   printf("%-5d", T-> key);
   inorder(T->R);
}

void BSTprn ( tnode *T )
{
   printf("    Preorder       : "); preorder(T); printf("\n");
   printf("    Inorder        : "); inorder(T); printf("\n");
}

void BSTfree ( tnode *T )
{
   if (T == NULL) return;
   BSTfree(T -> L);
   BSTfree(T -> R);
   free(T);
}

int BSTsame ( tnode *T, tnode *T1 )
{
   if ((T == NULL) && (T1 == NULL)) return 1;
   if (T == NULL) return 0;
   if (T1 == NULL) return 0;
   if (T -> key != T1 -> key) return 0;
   return ((BSTsame(T->L,T1->L)) && (BSTsame(T->R,T1->R))) ? 1 : 0;
}

void checkall ( seq S, int n, tnode *T )
{
   Lint i, nprob;
   tnode *T1;

   nprob = 0;
   for (i=0; i<S.cnt; ++i) {
      T1 = BSTcons(S.seq[i],n);
      if (!BSTsame(T,T1)) ++nprob;
      BSTfree(T1);
   }
   if (nprob) printf("    %Ld trees do not match\n", nprob);
   else printf("    All trees match\n");
}

int main ( int argc, char *argv[] )
{
   int n, *A;
   Lint i;
   seq S;
   tnode *T;

   srand((unsigned int)time(NULL));
   n = (argc > 1) ? atoi(argv[1]) : 10;
   printf("%d\n", n);

   A = genlist(n);

   printf("\n+++ Sequence count\n");
   printf("    Total number of sequences = %Lu\n", countseq(A,n));

   printf("\n+++ All sequences\n");
   S = findallseq(A,n);
   prnallseq(S,n);

   T = BSTcons(A,n);
   printf("\n+++ BST constructed from input array\n");
   BSTprn(T);

   printf("\n+++ Checking all sequences\n");
   checkall(S,n,T);

   BSTfree(T);
   for (i=0; i<S.cnt; ++i) free(S.seq[i]);
   free(S.seq);

   exit(0);
}