Is it possible to invert an array with constant extra space?

Question

Let's say I have an array A with n unique elements on the range [0, n). In other words, I have a permutation of the integers [0, n).

Is possible to transform A into B using O(1) extra space (AKA in-place) such that B[A[i]] = i?

For example:

       A                  B [3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4] 

Answer 1

Yes, it is possible, with O(n^2) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0. This is cycle leader algorithm.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from this index. If this cycle contains any index below the starting index, just skip it.

---

Or this O(n^3) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from all preceding indexes. If current index is present in any preceding cycle, just skip it.

---

I have written (slightly optimized) implementation of O(n^2) algorithm in C++11 to determine how many additional accesses are needed for each element on average if random permutation is inverted. Here are the results:

size accesses 2^10 2.76172 2^12 4.77271 2^14 6.36212 2^16 7.10641 2^18 9.05811 2^20 10.3053 2^22 11.6851 2^24 12.6975 2^26 14.6125 2^28 16.0617 

While size grows exponentially, number of element accesses grows almost linearly, so expected time complexity for random permutations is something like O(n log n).