#include <stdio.h>
char *permArray = NULL;
int **nkArray = NULL;
int factorial ( int n )
/* Returns n! (factorial of n) */
{
int retval = 1, i;
for (i=1;i<=n;i++) retval *= i;
return(retval);
}
void genPerm ( char **A , int n )
/* Generate the list of all permutations of 1,...,n from the list of
all permutations of 1,...,n-1 */
{
char *B = NULL;
int i,j,k,l,L,m;
if (n == 1) { /* Basis case : no previous list is available */
(*A) = (char *)malloc(sizeof(char));
(*A)[0] = 1;
return;
}
/* Now n > 1 and the list for n-1 is passed via A. This list is
to be modified to the list for n. The resulting list is again
saved in A. So it is necessary to reallocate memory to A. */
/* Length of the previous list */
l = (n-1)*factorial(n-1);
/* make a local copy of the previous list in B */
B = (char *)malloc(l*sizeof(char));
for (i=0;i<l;i++) B[i] = (*A)[i];
/* Now A can be rellaocated memory. One can use realloc() for that.
Here I free the memory assigned to A (actually *A) and then allocate
fresh memory to it. */
free(*A);
(*A) = NULL;
L = n * factorial(n); /* Size of the new list */
(*A) = (char *)malloc(L*sizeof(char));
/* Initialize : j is the index for reading from B and k is the index
for writing to A */
j = k = 0;
while (j<l) {
/* For each permutation of 1,...,n-1 one can insert n in n different
locations to get n different permutations of 1,...,n. */
for(i=0;i<n;i++) {
for (m=0;m<i;m++) (*A)[k++] = B[j+m]; /* Copy the first part */
(*A)[k++] = n; /* Insert n */
for (m=i;m<n-1;m++) (*A)[k++]=B[j+m]; /* Copy the remaining part */
}
j += n-1; /* Consider the next permutation of 1,...,n-1 */
}
free(B); /* Free local memory */
}
int countDescentEnum ( char *A , int n )
/* Enumerative counting of the Eulerian numbers <n,k> for k=0,...,n-1 */
{
int i,j,k,l;
int *ndesc; /* The numbers <n,k> are grown here */
ndesc = (int *)calloc(n,sizeof(int)); /* Allocate and intialize to zero */
l = n * factorial(n); /* Size of the list of permutations */
j = 0; /* j is the index for reading from A */
while (j<l) {
k=0; /* k counts the number of descents in this permutation */
for (i=0;i<n-1;i++)
if (A[j+i]>A[j+i+1]) /* A descent is detected */
k++; /* Increment k */
ndesc[k]++; /* k decsents have been found, record this info */
j+=n; /* Next permutation */
}
/* Print the Eulerian numbers <n,k> obtained by exhaustive enumeration */
printf("n = %d Enumerative ",n);
for (k=0;k<n;k++) printf(" %5d ",ndesc[k]);
printf("\n");
}
int rec ( int n , int k )
/* Implements the recursive definition of <n,k> */
{
if (k==0) return(1);
if (n<=k) return(0);
return((k+1)*rec(n-1,k)+(n-k)*rec(n-1,k-1));
}
int countDescentRec ( int n )
/* Recursive counting of the Eulerian numbers <n,k> for k=0,...,n-1 */
{
int k;
printf(" Recursive ");
for (k=0;k<n;k++) printf(" %5d ",rec(n,k));
printf("\n");
}
int countDescentIter ( int **A , int n )
/* Iterative counting of the Eulerian numbers <n,k> for k=0,...,n-1 */
{
int k;
if (n==1) A[1][0] = 1; /* Basis case */
else {
A[n][0] = 1; /* Basis case */
/* Use the values stored in A[n-1] to obtained A[n][k]. */
for (k=1;k<n-1;k++) A[n][k] = (k+1)*A[n-1][k]+(n-k)*A[n-1][k-1];
A[n][n-1] = 1; /* Using the recursive definition requires
reading A[n-1][n-1]. This array location
does not exist and this quantity has not
been computed. On the other hand, we know
that n,n-1,...,2,1 is the only permutation
of 1,...,n with n-1 descents. */
}
printf(" Iterative ");
for (k=0;k<n;k++) printf(" %5d ",A[n][k]);
printf("\n");
}
int main ()
{
int i,k,n,N=8;
printf(" ");
for (k=0;k<N;k++) printf(" k = %d ",k);
printf("\n");
/* Allocate memory to the array needed for the iterative method */
nkArray = (int **)malloc((N+1)*sizeof(int *));
nkArray[0] = NULL;
for (i=1;i<=N;i++) nkArray[i] = (int *)malloc(i*sizeof(int));
for (n=1;n<=N;n++) {
genPerm(&permArray,n); /* Generate the list of permutations
from the older list */
countDescentEnum(permArray,n); /* Enumerative counting */
countDescentRec(n); /* Recursive counting */
countDescentIter(nkArray,n); /* Iterative counting */
}
/* Free memory allocated to the array needed for the iterative memory */
for (i=1;i<=N;i++) free(nkArray[i]);
free(nkArray);
/* Free memory allocated to the permutation array */
free(permArray);
}
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7
n = 1 Enumerative 1
Recursive 1
Iterative 1
n = 2 Enumerative 1 1
Recursive 1 1
Iterative 1 1
n = 3 Enumerative 1 4 1
Recursive 1 4 1
Iterative 1 4 1
n = 4 Enumerative 1 11 11 1
Recursive 1 11 11 1
Iterative 1 11 11 1
n = 5 Enumerative 1 26 66 26 1
Recursive 1 26 66 26 1
Iterative 1 26 66 26 1
n = 6 Enumerative 1 57 302 302 57 1
Recursive 1 57 302 302 57 1
Iterative 1 57 302 302 57 1
n = 7 Enumerative 1 120 1191 2416 1191 120 1
Recursive 1 120 1191 2416 1191 120 1
Iterative 1 120 1191 2416 1191 120 1
n = 8 Enumerative 1 247 4293 15619 15619 4293 247 1
Recursive 1 247 4293 15619 15619 4293 247 1
Iterative 1 247 4293 15619 15619 4293 247 1
[Course home] [Home]