[PYTHON] Lassen Sie uns zufällig eine vollständige Sequenz generieren

In Mischen, bei dem sich alle Elemente bewegen (nicht an derselben Position bleiben) wurde argumentiert, dass nicht alle Muster angezeigt werden, also ich Ich habe auch ein wenig nachgedacht.

Wahrscheinlichkeit, in perfekter Ordnung zu sein

Dies ist das Problem der sogenannten [vollständigen Bestellung](https://ja.wikipedia.org/wiki/complete order) (Störungsreihenfolge, Störung).

[1, 2,\ldots, n]

Aufführen $[i_1, i_2, \ldots, i_n]$ Bei einer Neuanordnung als wird diejenige, die $ k \ neq i_k \ (k = 1, \ ldots, n) $ ist, als vollständige Sequenz bezeichnet. Wenn eine Liste von $ n $ zufällig sortiert wird, hat die Wahrscheinlichkeit, dass sie in voller Reihenfolge $ p_n $ ist, einen Extremwert von $ 1 / e $ ($ e $ ist ungefähr $ 2,71 $ in der Anzahl der Napiers). Es ist bekannt (Konvergenz ist auch sehr schnell) und $ p_3 = 1/3 $. Wenn also $ n \ geqq 3 $ ist, geht es darum $ \frac{1}{3} \leqq p_n\leqq \frac{1}{e} \fallingdotseq 0.367879 $ Die Ungleichung gilt. Mit anderen Worten, wenn Sie normal mischen, besteht eine Wahrscheinlichkeit von $ 1/3 $ oder mehr, dass es in perfekter Reihenfolge ist. Und wenn es keine perfekte Sequenz ist, können Sie sie höchstens $ 3 $ mischen, um eine nahezu perfekte Sequenz zu erhalten. Daher habe ich nicht viele Tricks, aber meine Schlussfolgerung war, das Mischen zu wiederholen, bis es in perfekter Reihenfolge war (lacht).

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: #Wenn es 0 enthält, ist es keine vollständige Sequenz
        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]

Ich konnte auch "[1, 0, 3, 2]" bestätigen.

Tote Geschichte

Das erste, was ich mir ausgedacht habe, war das obige, aber ich habe auch an die folgende Methode gedacht. Die Ausführungsgeschwindigkeit war jedoch langsam, so dass ich starb.

Mit einem konkreten Beispiel erklären $[a, b, c, d, e]$ Nach dem Zufallsprinzip sortieren $[a, b, e, d, c]$ Wenn, patrouillieren Sie $ a, b, d , die sich nicht bewegen $\begin{align} a \longmapsto b\\ b \longmapsto d\\ d \longmapsto a \end{align}$ Ersetzen Sie es durch $ [b, d, e, a, c] $$ Ist zu sein. Wenn dies der Fall ist, können Sie definitiv eine perfekte Sequenz erhalten, und es besteht die Möglichkeit, dass alle Muster herauskommen (obwohl die gleiche Gewissheit unbekannt ist). In diesem Fall kann jedoch nur $ 1 $, das nicht funktioniert hat, nicht überwacht werden. Daher muss es durch etwas anderes ersetzt werden, was den Code etwas kompliziert macht.