[PYTHON] Randomly generate a complete permutation

In shuffle where all elements move (do not remain in the same position), it was argued that not all patterns appear, so I I also thought about it a little.

Probability of perfect permutation

This is the so-called complete permutation (disturbance permutation, derangement) problem.

List $[i_1, i_2, \ldots, i_n]$ When rearranged as, the one that is $ k \ neq i_k \ (k = 1, \ ldots, n) $ is called a complete permutation. When a list of $ n $ is randomly sorted, the probability that it is in perfect permutation The limit value of $ p_n $ is $ 1 / e $ ($ e $ is about $ 2.71 $ in Napier number). It is known (convergence is also very fast), and $ p_3 = 1/3 $, so when $ n \ geqq 3 , it's about $ \frac{1}{3} \leqq p_n\leqq \frac{1}{e} \fallingdotseq 0.367879 $$ The inequality holds. In other words, if you shuffle normally, there is a probability of $ 1/3 $ or more that it is in perfect permutation. And if it's not a perfect permutation, you can get an almost perfect permutation by shuffling at most $ 3 $ times. Therefore, I don't have much tricks, but my conclusion was to repeat the shuffle until it became a perfect permutation (laughs).

import numpy as np

def derange(items):
    if not isinstance(items, np.ndarray):
        items = np.array(items)
    index = np.arange(items.size)
    rand_index = index.copy()
    while 0 in index - rand_index: #If it contains 0, it is not a perfect permutation
        np.random.shuffle(rand_index)
    return items[rand_index]

for i in range(100):
    print(derange(range(4)))

out

[1 0 3 2]
[3 2 0 1]
[1 2 3 0]
[3 2 0 1]
[2 3 1 0]
[3 0 1 2]
[3 2 0 1]
[2 3 1 0]
[1 2 3 0]
[3 2 1 0]
[1 2 3 0]
[2 0 3 1]
[3 2 0 1]
[2 3 1 0]
[3 2 0 1]
[2 3 1 0]
[1 3 0 2]
[1 3 0 2]
[3 2 1 0]
[2 3 0 1]
[2 3 0 1]
[2 0 3 1]
[1 3 0 2]
[1 0 3 2]
[2 3 1 0]
[2 3 0 1]
[1 2 3 0]
[3 2 1 0]
[3 0 1 2]
[2 3 0 1]
[1 2 3 0]
[2 0 3 1]
[3 2 1 0]
[3 2 1 0]
[3 2 1 0]
[1 0 3 2]
[1 2 3 0]
[2 3 1 0]
[3 0 1 2]
[1 2 3 0]
[1 3 0 2]
[2 3 1 0]
[2 3 1 0]
[1 2 3 0]
[2 3 1 0]
[1 2 3 0]
[3 2 1 0]
[3 2 0 1]
[2 0 3 1]
[1 0 3 2]
[2 3 1 0]
[1 2 3 0]
[2 3 0 1]
[1 2 3 0]
[2 3 0 1]
[2 3 1 0]
[3 2 0 1]
[3 2 0 1]
[3 0 1 2]
[3 2 1 0]
[2 3 1 0]
[2 0 3 1]
[1 0 3 2]
[1 2 3 0]
[2 0 3 1]
[1 2 3 0]
[2 3 1 0]
[3 2 1 0]
[1 2 3 0]
[2 0 3 1]
[3 0 1 2]
[1 0 3 2]
[3 0 1 2]
[3 2 1 0]
[1 0 3 2]
[3 2 0 1]
[2 3 0 1]
[2 3 1 0]
[2 3 1 0]
[2 3 1 0]
[1 0 3 2]
[3 2 0 1]
[1 0 3 2]
[1 2 3 0]
[1 0 3 2]
[2 3 1 0]
[1 0 3 2]
[1 2 3 0]
[1 2 3 0]
[2 3 1 0]
[3 0 1 2]
[3 0 1 2]
[3 2 1 0]
[3 0 1 2]
[2 0 3 1]
[1 2 3 0]
[1 3 0 2]
[2 3 1 0]
[2 3 0 1]
[3 0 1 2]

I was also able to confirm [1, 0, 3, 2].

Dead story

The first thing I came up with was the one above, but I also thought of the following method. However, the execution speed was slow, so I died.

To explain with a concrete example $[a, b, c, d, e]$ Randomly sort $[a, b, e, d, c]$ If, patroll $ a, b, d $ that are not moving $\begin{align} a \longmapsto b\\\\ b \longmapsto d\\\\ d \longmapsto a \end{align}$ Replace it with $ [b, d, e, a, c] $ Is to be. If this is the case, you can definitely get a perfect permutation, and there is a possibility that all patterns will come out (although the same certainty is unknown). However, in this case, if there are only $ 1 $ that did not work, it cannot be patrolled, so it is necessary to replace it with something else, which makes the code a little complicated.