[PYTHON] Générons aléatoirement une séquence complète

Dans mélanger où tous les éléments se déplacent (ne restent pas dans la même position), il a été soutenu que tous les modèles n'apparaissent pas, donc je J'ai aussi réfléchi un peu.

Probabilité d'être en parfait ordre

C'est le problème du soi-disant [ordre parfait](https://ja.wikipedia.org/wiki/perfect order) (ordre de perturbation, dérangement).

liste $[i_1, i_2, \ldots, i_n]$ Lorsqu'il est réorganisé comme, celui qui est $ k \ neq i_k \ (k = 1, \ ldots, n) $ est appelé une séquence complète. Lorsqu'une liste de $ n $ est triée aléatoirement, la probabilité qu'elle soit dans le plein ordre $ p_n $ a une valeur extrême de $ 1 / e $ ($ e $ est d'environ 2,71 $ en nombre Napier). C'est connu (la convergence est aussi très rapide), et $ p_3 = 1/3 $, donc quand $ n \ geqq 3 , il s'agit de $ \frac{1}{3} \leqq p_n\leqq \frac{1}{e} \fallingdotseq 0.367879 $$ L'inégalité tient. En d'autres termes, si vous mélangez normalement, il y a une probabilité de 1/3 $ ou plus qu'il soit dans un ordre parfait. Et si ce n'est pas une séquence parfaite, vous pouvez la mélanger au maximum à 3 $ pour obtenir une séquence presque parfaite. Par conséquent, je n'ai pas beaucoup d'astuces, mais ma conclusion a été de répéter le mélange jusqu'à ce qu'il soit en parfait état (rires).

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: #S'il contient 0, ce n'est pas une séquence complète
        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]

J'ai également pu confirmer «[1, 0, 3, 2]».

Histoire morte

La première chose que j'ai trouvée était celle ci-dessus, mais j'ai aussi pensé à la méthode suivante. Cependant, la vitesse d'exécution était lente, alors je suis mort.

Expliquer avec un exemple concret $[a, b, c, d, e]$ Trier au hasard $[a, b, e, d, c]$ Si, patrouillent $ a, b, d $ qui ne bougent pas $\begin{align} a \longmapsto b\\\\ b \longmapsto d\\\\ d \longmapsto a \end{align}$ Remplacez-le par $ [b, d, e, a, c] $ Est d'être. Si tel est le cas, vous pouvez certainement obtenir une séquence parfaite, et il est possible que tous les modèles sortent (bien que la même certitude soit inconnue). Cependant, dans ce cas, s'il n'y a que $ 1 $ qui n'a pas fonctionné, il ne peut pas être patrouillé, il est donc nécessaire de le remplacer par quelque chose d'autre, ce qui rend le code un peu compliqué.