Chapter 7

Exercise 7.1

All algorithms run in $\Theta(N)$ time without trying to reconstruct the associated permutation.

• left-to-right maxima: Traverse the inversion table from left to right and register indices where $q_k=0$.

• right-to-left minima: Record the index of the last entry in the list of left-to-right minima (see the book); this is the index of an absolute minimum. Store this index and set the counter variable $c=1$. Traverse the inversion table from this index from left to right and seek for an element where $k-c-q_k=1$. Prepend $k$ to the current list, increase the counter by one, and repeat the process until reaching the last element. Prepend the index $N$, since the last element from the right is the first seen minima.

• right-to-left maxima: Record the index of the last entry in the list of left-to-right maxima; this is the index of an absolute maximum (see the first item in this list). Store this index $m$ and set the counter variable $c=1$. Traverse the inversion table from $m+1$ to $N-1$ and store the maximal index of every encountered value of $q_k$ along the way. We need this lookup table in the next stage. Repeat the following 3 steps until $c=q_N$: Seek for an index $k$ where $q_k=c$ using our lookup table. If there is a match and $k$ is greater than the last recorded index, then prepend $k$ to the current list. Increase $c$ by one. Prepend the index $N$, since the last element from the right is the first seen maxima.

Exercise 7.2

Let $m$ be the number of cycles in the permutation and denote by $l_k$ the length of the $k$th cycle. The number of ways to write the sample permutation in cycle notation is $m! \prod_{k=1}^m l_k$.

Exercise 7.3

There are $\binom{2N}{N}((N-1)!)^2/2$ permutations of $2N$ elements having exactly two cycles, each of length $N$.

There are $\binom{2N}{N}N!/2^N=(2N-1)!!$ permutations of $2N$ elements having exactly $N$ cycles, each of length 2. Notice that we must divide by $2^N$, since for a given representation all other possible ways of "flipping" elements in those 2 cycles are duplicates.

Exercise 7.4

We must maximize the product from Exercise 2 subject to the constraint $\sum_{k=1}^m l_k = N$. The formula depends on the number of cycles and the product of their lengths. If we increase $m$ then we reduce the lengths and vice versa. Nonetheless, the contribution of $m$ is more important, as it grows factorially.

Let’s assume that we start with an identity permutation with $m=N$. This results in $N!$ equivalent representations. Can we maximize this number? If we set only one cycle to length 2 and keep the others at 1, then we get $(N-1)!2<N!$. It turns out that we cannot attain a better result.

Therefore, the identity permutation has the greatest number of different representations with cycles.

Exercise 7.5

The Python 3 program below implements the task in $\Theta(N^2)$ time.

def nis(p):
    """Returns the table s with s[i] the number of increasing subsequences that begin at position i."""
    n = len(p)
    s = [0] * n
    for i in range(n - 1, -1, -1):
        s[i] = 1
        for j in range(i + 1, n):
            if p[j] > p[i]:
                s[i] += s[j]
    return s

if __name__ == '__main__':
    p = [9, 14, 4, 1, 12, 2, 10, 13, 5, 6, 11, 3, 8, 15, 7]
    print(nis(p))

It outputs [18, 2, 40, 86, 4, 41, 6, 2, 14, 7, 2, 5, 2, 1, 1].

The example in the book is wrong. The reported errata only covers two problematic entries, but evidently there are more.

Exercise 7.6