Random Derangement

Given a positive integer n, generate a length-n array A uniformly at random subject to A[i] != i – 1.

Solution:

One simple solution is to generate a random permutation and then reject the one with a fixed point. There is another solution without rejection [1].

Reference: Stackoverflow, Stackoverflow

[1] Kenji Mikawa, Ken Tanaka, Linear-time generation of uniform random derangements encoded in cycle notation, Discrete Applied Mathematics