The amortized complexity of std::next_permutation?_问答_开发者

I just read this other question about the complexity of next_permutation and while I'm satisfied with the response (O(n)), it seems like开发者_JS百科 the algorithm might have a nice amortized analysis that shows a lower complexity. Does anyone know of such an analysis?

So looks like I'm going to be answering my own question in the affirmative - yes, next_permutation runs in O(1) amortized time.

Before I go into a formal proof of this, here's a quick refresher on how the algorithm works. First, it scans backwards from the end of the range toward the beginning, identifying the longest contiguous decreasing subsequence in the range that ends at the last element. For example, in 0 3 4 2 1, the algorithm would identify 4 2 1 as this subsequence. Next, it looks at the element right before this subsequence (in the above example, 3), then finds the smallest element in the subsequence larger than it (in the above example, 4). Then, it exchanges the positions of those two elements and then reverses the identified sequence. So, if we started with 0 3 4 2 1, we'd swap the 3 and 4 to yield 0 4 3 2 1, and would then reverse the last three elements to yield 0 4 1 2 3.

To show that this algorithm runs in amortized O(1), we'll use the potential method. Define Φ to be three times the length of the longest contiguously decreasing subsequence at the end of the sequence. In this analysis, we will assume that all the elements are distinct. Given this, let's think about the runtime of this algorithm. Suppose that we scan backwards from the end of the sequence and find that the last m elements are part of the decreasing sequence. This requires m + 1 comparisons. Next, we find, of the elements of that sequence, which one is the smallest larger than the element preceding this sequence. This takes in the worst case time proportional to the length of the decreasing sequence using a linear scan for another m comparisons. Swapping the elements takes, say, 1 credit's worth of time, and reversing the sequence then requires at most m more operations. Thus the real runtime of this step is roughly 3m + 1. However, we have to factor in the change in potential. After we reverse this sequence of length m, we end up reducing the length of the longest decreasing sequence at the end of the range to be length 1, because reversing the decreasing sequence at the end makes the last elements of the range sorted in ascending order. This means that our potential changed from Φ = 3m to Φ' = 3 * 1 = 3. Consequently, the net drop in potential is 3 - 3m, so our net amortized time is 3m + 1 + (3 - 3m) = 4 = O(1).

In the preceding analysis I made the simplifying assumption that all the values are unique. To the best of my knowledge, this assumption is necessary in order for this proof to work. I'm going to think this over and see if the proof can be modified to work in the case where the elements can contain duplicates, and I'll post an edit to this answer once I've worked through the details.

I am not really sure of the exact implementation of std::next_permutation, but if it is the same as Narayana Pandita's algorithm as desribed in the wiki here: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations,

assuming the elements are distinct, looks like it is O(1) amortized! (Of course, there might be errors in the below)

Let us count the total number of swaps done.

We get the recurrence relation

T(n+1) = (n+1)T(n) + Θ(n²)

(n+1)T(n) comes from fixing the first element and doing the swaps for the remaining n.

Θ(n²) comes from changing the first element. At the point we change the first element, we do Θ(n) swaps. Do that n times, you get Θ(n²).

Now let X(n) = T(n)/n!

Then we get

X(n+1) = X(n) + Θ(n²)/(n+1)!

i.e there is some constant C such that

X(n+1) <= X(n) + Cn²/(n+1)!

Writing down n such inequalities gives us

X(n+1) - X(n) <= Cn²/(n+1)!

X(n) - X(n-1) <= C(n-1)²/(n)!

X(n-1) - X(n-2) <= C(n-2)²/(n-1)!

...

X(2) - X(1) <= C1²/(1+1)!

Adding these up gives us X(n+1) - X(1) <= C(\sum j = 1 to n (j^2)/(j+1)!).

Since the infinite series \sum j = 1 to infinity j^2/(j+1)! converges to C', say, we get X(n+1) - X(1) <= CC'

Remember that X(n) counts the average number of swaps needed (T(n)/n!)

Thus the average number of swaps is O(1).

Since finding the elements to swap is linear with the number of swaps, it is O(1) amortized even if you take other operations into consideration.

Here n stands for the count of elements in the container, not the total count of possible permutations. The algorithm must iterate through an order of all elements at each call; it takes a pair of bidirectional iterators, which implies that to get to one element the algorithm must first visit the one before it (unless its the first or last element). A bidirectional iterator allows iterating backwards, so the algorithm can (must, in fact) perform half as many swaps as there are elements. I believe the standard could offer an overload for a forward iterator, which would support dumber iterators at the cost of n swaps rather than half n swaps. But alas, it didn't.

Of course, for n possible permutations the algorithm operates in O(1).