algorithm - in-place permutation of a array follows this rule - Stack Overflow

An O(n) time O(1) space solution.

The ideas used are similar to the ideas used in the following paper: A simple in-place algorithm for Inshuffle.

You would need to read that paper to understand the below. I suggest you also read: http://stackoverflow.com/questions/2352542/how-to-master-in-place-array-modification-algorithms

This is basically the inverse permutation of what is solved in the paper above.

It is enough to solve this when 2n+1 is a power of 3 = (3^m say), as we can use divide and conquer after that (like the O(nlogn) solution).

Now 2n+1 and n+1 are relatively prime, so working modulo 3^m, we see that n+1 must be some power of 2. (See that paper again to see why: basically any number modulo 3^m which is relative prime to 3^m is a power of 2, again modulo 3^m).

Say n+1 = 2^k (we don't know k yet and note this is modulo 3^m).

A way to find out k, compute powers of n+1 modulo 3^m, till it becomes 1. This gives us k (and is O(n) time at most).

Now we can see that the cycles of the permutation (see above paper/stackoverflow link for what that is) start at

2^a*3^b

where 0 <= a < k, and 0 <= b < m.

So you start with each possible pair (a,b) and follow the cycles of the permutation, and this gives an O(n) time, in-place algorithm, as you touch each element no more than a constant number of times!

This was a bit brief(!) and if you need more info, please let me know.

Read full article from algorithm - in-place permutation of a array follows this rule - Stack Overflow