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).

[1, 2,\ldots, n]

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é.

Recommended Posts

Générons aléatoirement une séquence complète
Code qui génère un score au hasard
[Python] Générer de manière aléatoire un grand nombre de noms de personne en anglais
Générer une image Docker à l'aide de Fabric
Générer une distribution normale avec SciPy
Générer une URL pré-signée avec golang
[Python] Générer un mot de passe avec Slackbot
Metaclass (wip) pour générer un dictionnaire
Générer une liste de caractères consécutifs
Générer un badge d'affichage du nombre de téléchargements de la bibliothèque Python
python + faker Générer aléatoirement un point avec un rayon de 100m à partir d'un certain point