how to verify permutation generated in constant amortized time?

Question

Here is an algorithm that generates the next permutation in lexicographic order, changing the given permutation in-place:

1. Find the largest index k such that a[k] < a[k+1]. If no such index exists, exit (the permutation is the last permutation).
2. Find the largest index l such that a[k] < a[l].
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k+1] up to and including the final element a[n].

Is the next permutation generated in constant amortized time and if yes, how to verify it?

Answer 1

For a number $m$, let $\alpha(m) = \max \{ k : k! | m \}$. This sequence starts at $\infty,1,2,1,2,1,3,\ldots$. I claim that in iteration $t$ of the algorithm (where $1 \leq t \leq n!-1$), we have $n-1-k = \alpha(t)$. The average value of $\alpha(m)$ is roughly $$ \left(1 - \frac{1}{2}\right) 1 + \left(\frac{1}{2} - \frac{1}{6}\right) 2 + \left(\frac{1}{6} - \frac{1}{24}\right) 3 + \cdots = \\ 1 + \frac{1}{2} + \frac{1}{6} + \cdots = e-1. $$ Since the running time of each step of the algorithm is proportional to $n-1-k$, we get that the algorithm runs in constant amortized time.

It remains to prove the claim $n-1-k = \alpha(t)$, which I leave to the OP.

Answer 2

Already posted:

• finding $l$ costs $n-k$
• swap costs $3$
• reversing costs $2(n-k)$

Thus, having found $k$ we do $3(n-k+1)$ steps.

In order to find $k$, we need to do $n-k$ comparisons which costs $2(n-k)$. Observe that after reversing, the tail of our permutation is increasing, so we only need to fix the first $k$ elements at most. This gives us that each $k$ is looked up at most $\frac{n!}{(n-k)!}$ times. Now we can get an upper bound on the total cost: \begin{align*} \sum_{k=1}^{n-1} \frac{n!}{(n-k)!} \cdot 3(n-k+1) &\leq 3\sum_{k=1}^{n-1} \frac{n!}{(n-k)!} \cdot (n-k+1) \\ &\leq 3\cdot\sum_{k=1}^{n-1} \frac{n!}{(n-k-1)!} \cdot \frac{n-k+1}{n-k} \\ &\leq 3\cdot\sum_{k=2}^{n-1} \frac{n!}{(n-k)!} \cdot 2 \\ &\leq 6 \cdot n!\cdot\sum_{k=2}^{n-1} \frac{1}{(n-k)!} \\ &< 6 \cdot n!\cdot e \end{align*}

Thus, we obtain $O(n!)$ after all. Since there are $n!$ permutations, the amortized time to produce the next one is constant.