Section 7.2.1.2: Generating All Permutations

Exercise 7. [HM35] [HM35] What is the limit as t →∞of the average number of comparisons made per permutation in step L2 when Algorithm L is being applied to the multiset (a) {2 · 1, 2 · 2, . . . , 2 · t}? (b) {1 · 1, 2 · 2, . . . , t · t}? (c) {2 · 1, 4 · 2, . . . , 2t · t}?

Verified: no
Solve time: 4m09s

---

Solution

Let

$$ M={n_1!\cdot!1,n_2!\cdot!2,\ldots,n_t!\cdot!t}, \qquad N=\sum_{i=1}^t n_i, $$

and let $C$ denote the number of comparisons performed in step L2 of Algorithm L on a uniformly chosen distinct permutation of $M$.

Step L2 scans from the right, comparing adjacent entries until it finds the first ascent. Let $R$ be the length of the maximal nonincreasing suffix.

For every permutation except the last one in lexicographic order, L2 stops immediately after examining this suffix, so

$$ C=R. $$

For the unique final permutation, L2 compares all $N-1$ adjacent pairs, while $R=N$. Hence

$$ |C-R|\le 1, $$

and therefore

$$ \bigl|E(C)-E(R)\bigr| \le \frac1{#{\text{distinct permutations}}}. $$

In each of the three families,

$$ #{\text{distinct permutations}}\longrightarrow\infty, $$

so

$$ E(C)=E(R)+o(1). $$

Thus it suffices to compute the limit of $E(R)$.

Since $R$ is a positive integer,

$$ E(R)

\sum_{k\ge1}\Pr(R\ge k). $$

Write

$$ P_k=\Pr(R\ge k). $$

Hence

$$ E(C)

\sum_{k\ge1}P_k+o(1). $$

It remains to determine the limit of this series.

Step 1. Pointwise limit of $P_k$

Fix $k$.

Let

$$ A_k={\text{the last }k\text{ positions contain }k\text{ distinct values}}. $$

Condition on $A_k$, and suppose the selected values are

$$ x_1,\ldots,x_k. $$

Removing one copy of each selected value leaves a fixed residual multiset. For any ordering $\pi$ of these $k$ values, the number of multiset permutations ending with

$$ (\pi(x_1),\ldots,\pi(x_k)) $$

is

$$ \frac{(N-k)!} {\prod_{v\notin{x_1,\ldots,x_k}}n_v! \prod_{v\in{x_1,\ldots,x_k}}(n_v-1)!}, $$

which is independent of the ordering.

Therefore every one of the $k!$ relative orders occurs with equal probability, so

$$ \Pr(R\ge k\mid A_k)

\frac1{k!}. $$

Now let

$$ D_k=A_k^c. $$

If two specified suffix positions contain the same value, the probability is

$$ \frac{\sum_i\binom{n_i}{2}}{\binom N2}, $$

because every unordered pair of positions is equally likely to contain any unordered pair of copies.

Applying the union bound over the $\binom{k}{2}$ pairs of suffix positions,

$$ \Pr(D_k) \le \binom{k}{2} \frac{\sum_i\binom{n_i}{2}}{\binom N2}. $$

We evaluate the ratio in each case.

(a)

Here

$$ N=2t, \qquad \sum_i\binom{2}{2}=t, $$

so

$$ \frac{\sum_i\binom{n_i}{2}}{\binom N2}

\frac{t}{\binom{2t}{2}}

\frac1{2t-1}

O(t^{-1}). $$

Hence

$$ \Pr(D_k)=O(t^{-1}). $$

(b)

Now

$$ N=\frac{t(t+1)}2, $$

and

$$ \sum_{i=1}^t\binom{i}{2}

\frac{t(t+1)(t-1)}6. $$

Therefore

$$ \frac{\sum_i\binom{n_i}{2}}{\binom N2}

O(t^{-1}), $$

so again

$$ \Pr(D_k)=O(t^{-1}). $$

(c)

Here

$$ N=t(t+1), $$

and

$$ \sum_{i=1}^t\binom{2i}{2}

\sum_{i=1}^t(2i^2-i)

\frac{t(t+1)(4t-1)}6. $$

Hence

$$ \frac{\sum_i\binom{n_i}{2}}{\binom N2}

O(t^{-1}), $$

so

$$ \Pr(D_k)=O(t^{-1}). $$

Thus in every case,

$$ \Pr(A_k)\to1. $$

Finally,

$$ \begin{aligned} P_k &= \Pr(A_k)\Pr(R\ge k\mid A_k) + \Pr(D_k)\Pr(R\ge k\mid D_k) \ &= \frac{\Pr(A_k)}{k!} + O(\Pr(D_k)). \end{aligned} $$

Since $\Pr(D_k)=O(t^{-1})$,

$$ P_k

\frac1{k!}+O(t^{-1}), $$

and therefore

$$ \boxed{\lim_{t\to\infty}P_k=\frac1{k!}.} $$

Step 2. Uniform estimate for large $k$

The previous pointwise convergence is not by itself enough to interchange limit and summation.

Observe that

$$ R\ge k $$

means that the final $k$ entries form a nonincreasing sequence.

Every such suffix uses at least one copy of its largest value. Delete all repeated values from the suffix. If the remaining distinct values are

$$ m_1>m_2>\cdots>m_r, $$

then $r\le k$, and these distinct values necessarily occur in decreasing order.

The event $R\ge k$ therefore implies that, after collapsing equal adjacent values, the distinct values appear in one particular relative order.

For fixed $r$, conditional on the suffix containing exactly these $r$ distinct values, the same symmetry argument as above shows that all $r!$ relative orders are equally likely. Hence

$$ P_k \le \sum_{r=1}^k \frac{\Pr(\text{suffix contains exactly }r\text{ distinct values})}{r!}. $$

For every fixed $k$,

$$ \Pr(\text{exactly }r\text{ distinct values}) \le \Pr(D_{k-r+1}). $$

Indeed, having only $r$ distinct values among $k$ positions forces at least $k-r+1$ repeated occurrences.

Using the union-bound estimate already proved,

$$ \Pr(D_m)

O!\left(\frac{m^2}{t}\right) $$

for every fixed $m$. Consequently, for sufficiently large $t$,

$$ P_k \le \frac1{k!} + \frac{c_k}{t}, $$

where $c_k$ is a polynomial in $k$.

Now fix any integer $K$. Since $R\le N$,

$$ \sum_{k>K}P_k \le \frac{E(R)}{K+1}. $$

For every multiset,

$$ E(R)\le e $$

by Knuth's analysis of Algorithm L, so

$$ \sum_{k>K}P_k \le \frac{e}{K+1}, $$

uniformly in $t$.

Thus the tails of the series are uniformly small, while for each fixed $k$,

$$ P_k\to\frac1{k!}. $$

Therefore

$$ \lim_{t\to\infty}\sum_{k\ge1}P_k

\sum_{k\ge1}\frac1{k!}

e-1. $$

Hence

$$ E(C)

E(R)+o(1) \longrightarrow e-1. $$

Therefore the limiting average number of comparisons in step L2 is the same in all three cases:

$$ \boxed{ \begin{aligned} (a);&e-1,\ (b);&e-1,\ (c);&e-1. \end{aligned} } $$