2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ I suggest you run this algorithm for small values of $n$. This will allow you to check whether it indeed generates the next permutation in lexicographic order, and will allow you to measure the average number of operations per step. If this average doesn't increase with $n$, then probably the algorithm takes constant amortized time. Looking at the pattern of the running times for small values of $n$ will probably help with the proof. $\endgroup$ Sep 25, 2014 at 17:44
  • 1
    $\begingroup$ More concretely, the running time of each step is $O(n-k)$, so I suggest you understand how the quantity $n-k$ changes as we go over all permutations for small $n$. $\endgroup$ Sep 25, 2014 at 17:45

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.