But if you are through with Assigment 7, here is a bonus exercise for you. (Bonus means that any marks you get for this exrecise will be added to your total (after scaling, of course), but the marks for this exercise will not be added to the total credit for the lab.)
[Permutations and runs]
123132213231312321where each element (of {1,...,n}) occupies a cell in the array. Thus the size of the array will be n! times n. If n is known, we do not need separator between two permutations, since the size of each permutation is exactly known.
If you choose, you can use a two-dimensional array for storing the permutations. In that case a natural strategy is to store a permutation in each row and have n! rows to store all the permutations. For n=3 the 2-D array would look like:
123 132 231 213 312 321
257183496are
257, 18, 349, 6.Note that every run (except the last) is followed by a descent (also called a fall). For example, in the above permutation the descents are 71, 83 and 96. It is clear that if a permutation has k+1 runs, then it has exactly k descents, and conversely. Let us denote by the notation
<n,k>the number of permutations of 1,...,n with exactly k descents. The numbers <n,k> are called Eulerian numbers. The following table shows all the permutations of 1,2,3,4 and the runs and descents in each permutation. This list gives us the values of <4,k>.
Use the list of all permutations obtained from the previous step to enumerate <n,k> for n=1,...,8 and k=0,1,...,n-1.
<n,0> = 1. <n,k> = 0, if k >= n. <n.k> = (k+1)<n-1,k> + (n-k)<n-1,k-1>, otherwise.Write a recursive function to compute <n,k> for n=1,...,8 and k=0,1,...,n-1.
Format of output
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 n = 1 Enumerative x Recursive x Iterative x n = 2 Enumerative x x Recursive x x Iterative x x n = 3 Enumerative x x x Recursive x x x Iterative x x x n = 4 Enumerative x xx xx x Recursive x xx xx x Iterative x xx xx x n = 5 Enumerative x xx xx xx x Recursive x xx xx xx x Iterative x xx xx xx x n = 6 Enumerative x xx xxx xxx xx x Recursive x xx xxx xxx xx x Iterative x xx xxx xxx xx x n = 7 Enumerative x xxx xxxx xxxx xxxx xxx x Recursive x xxx xxxx xxxx xxxx xxx x Iterative x xxx xxxx xxxx xxxx xxx x n = 8 Enumerative x xxx xxxx xxxxx xxxxx xxxx xxx x Recursive x xxx xxxx xxxxx xxxxx xxxx xxx x Iterative x xxx xxxx xxxxx xxxxx xxxx xxx x
Best of luck for the EndSem. And also for all programming endeavors that you will undertake in future. We hope that these practice sessions will prove to be useful!!!
[Course home] [Home]