I guess some guys share the same confusion about the magic formula (2*i+1)%(n|1) in the brilliant solution by @StefanPochmann
Hereby I would like to share my thought process about how to prove the correctness of this formula.
To begin with, let's start from a simple example:
Given index 0,1,...,8, we would like to have rewired indices as below: [1,3,5,7,0,2,4,6,8] On the magic formula, look at the first part 2*i+1: it means for i and i+1, A(i+1) = A(i) + 2 when A(i+1) < n. Hence we will start from 1,3,5,... If n is odd, 1,3,5,... will end up with n%n = 0 then the sequence will become 1,3,5,...,n-2,0,2,4,... Note that upper bound of i is n-1, hence the sequence will end with: (2*(n-1)+1)%n equivalent to 2*(n-1) + 1 - n = n-1 For now we can see how this magic formula works if n is odd. The mapped sequence of indices will be: [1,3,5,...,n-2,0,2,4,...,n-1]
After the discussion on n is odd, we can easily discuss the situation when n is even:
If we still mod n instead of n+1, of course we still start from 1,3,5,... But notice that to make the formula work, the mapped sequence will reach n-2, which is even; then turn to 0,2,4,...,n-1, where n-1 is odd. Hence we definitely need to alter n to n+1.
Hope this post may help someone.
Thanks much for this brilliant solution.