When \(N = 2K\) is even, one can notice the following property (e.g. by looking at results of \(\mathrm{shuffle}\) for small \(N\)):

• for a pair of consecutive indices \(2i - 1, 2i\), after \(\mathrm{shuffle}(1, 2K)\) either \(A_{2i - 1} = 2i - 1\), \(A_{2i} = 2i\), or \(A_{2i - 1} = 2i\), \(A_{2i} = 2i - 1\).

In other words, \(\mathrm{shuffle}(1, 2K)\) operates independently on disjoint pairs of adjacent elements.

We prove this by induction, \(N = 2\) is trivial. When \(N = 2K > 2\), looking two steps deep, \(\mathrm{shuffle}(1, 2K)\) consists of:

• \(\mathrm{shuffle}(1, 2K - 2)\),
• \(\mathrm{shuffle}(2, 2K - 1)\),
• \(\mathrm{shuffle}(2, 2K - 1)\),
• \(\mathrm{shuffle}(3, 2K)\).

By assumption, \(\mathrm{shuffle}(2, 2K - 1)\) simply swaps some pairs, thus two middle steps cancel out. The remaining two \(\mathrm{shuffle}\)’s can be seen to still operate on pairs \(2i - 1, 2i\), thus the induction step is established.

By redefining \(\mathrm{shuffle}(L, L + 2K - 1)\) for \(2K > 2\) to be “\(\mathrm{shuffle}(L, L + 2K - 3)\) followed by \(\mathrm{shuffle}(L + 2, L + 2K - 1)\)”, we find that for any \(i = 1, \ldots, K\) the routine \(\mathrm{shuffle}(1, 2K)\) swaps the pair \(2i - 1, 2i\) exactly \({K - 1 \choose i - 1}\) times. Then, \(A_i\) is equal to \(i\) when the respective binomial coefficient above is even, or to the other element of \(i\)’s pair when the binomial is odd. We can use the fact that \({n \choose k}\) is odd if and only if \((n \& k) = k\), where \(\&\) is bitwise AND.

To solve the problem when \(N\) is odd, we can simply reduce to two even-length calls, which are solved as above.