Effizienter Algorithmus zur Erzeugung zweier diffuser, gestörter Permutationen eines Multisets nach dem Zufallsprinzip

Hintergrund

$\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr$ Angenommen, ich habe zwei identische Stapel von Murmeln. Jeder Marmor kann eine der Farben , wobei . Es sei die Anzahl der Murmeln der Farbe in jeder Charge. $n$ $c$ $c≤n$ $n_i$ $i$

Lassen $\msS$ die multiset sein $\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\}$ für eine Charge. In der Frequenzdarstellung kann $\msS$ auch geschrieben werden als $(\po^{n_1} \;\pt^{n_2}\; … \;\pc^{n_c})$ .

Die Anzahl der unterschiedlichen Permutationen von $\msS$ wird durch das Multinom angegeben :

| S S | = (n n 1 , n 2 , \dots , n c) = n ! n 1 ! n 2 ! \dots n c ! = n! \prod i = 1 c 1 n i ! .

$\left|\mfS_{\msS}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$

Frage

Gibt es einen effizienten Algorithmus, um zwei diffuse, gestörte Permutationen $P$ und $Q$ von $\msS$ zufällig zu erzeugen ? (Die Verteilung sollte gleichmäßig sein.)

Eine Permutation $P$ ist diffus, wenn für jedes einzelne Element $i$ von $P$ die Instanzen von $i$ ungefähr gleichmäßig in $P$ .
Angenommen, $\msS=(\po^4\;\pt^4)=\{\po,\po,\po,\po,\pt,\pt,\pt,\pt\}$ .
- $\{\po, \po, \po, \pt, \pt, \pt, \pt, \po\}$ ist nicht diffus
- $\{\po, \pt, \po, \pt, \po, \pt, \po, \pt\}$ ist diffus
Strenger:
- Wenn $n_i=1$ , gibt es nur eine Instanz von $i$ , die in "abgesetzt" werden kann $P$ , also sei $\Delta(i)=0$ .
- Andernfalls wäre $d(i,j)$ der Abstand zwischen Instanz $j$ und Instanz - $j+1$ von $i$ in $P$ . Subtrahieren Sie den erwarteten Abstand zwischen den Instanzen von $i$ , indem Sie Folgendes definieren: $δ (i, j) = d (i, j) - n n i Δ (i) = \sum j = 1 n i - 1 δ (i, j) 2$ $\delta(i,j)=d(i,j)-\frac n{n_i}\qquad\qquad\Delta(i)=\sum_{j=1}^{n_i-1} \delta(i,j)^2$ Wenn $i$ in gleichmäßig beabstandet ist $P$ , sollte $\Delta(i)$ Null sein, oder sehr nahe bei Null, wenn $n_i\nmid n$ .
Definieren Sie nun die Statistik , um zu messen, wie viel jedes in gleichmäßig verteilt ist . Wir nennen diffus, wenn nahe Null ist, oder ungefähr . (Man kann eine Schwelle wählen, die spezifisch für so dass diffus ist, wenn .) $s(P)=\sum_{i=1}^c\Delta(i)$ $i$ $P$ $P$ $s(P)$ $s(P)\ll n^2$ $k\ll1$ $\msS$ $P$ $s(P)<kn^2$

Diese Einschränkung erinnert an ein strengeres Echtzeit-Planungsproblem, das als Pinwheel-Problem bezeichnet wird, mit Multiset (so dass ) und Dichte . Ziel ist es, eine zyklische unendliche Folge so dass jede Teilfolge der Länge mindestens eine Instanz von . Mit anderen Worten, ein praktikabler Zeitplan erfordert alle ; wenn dicht ist ( ), dann ist und . Das Windradproblem scheint NP-vollständig zu sein. $\ms A=n/\msS$ $a_i=n/n_i$ $\rho=\sum_{i=1}^c n_i/n=1$ $P$ $a_i$ $i$ $d(i,j)≤a_i$ $\ms A$ $\rho= 1$ $d(i,j)=a_i$ $s(P)=0$
Zwei Permutationen und sind gestört, wenn eine Störung von ; das heißt, für jeden Index . $P$ $Q$ $P$ $Q$ $P_i ≠ Q_i$ $i\in[n]$
Angenommen, . $\msS=(\po^2\;\pt^2)=\{\po,\po,\pt,\pt\}$
- $\{\po, \pt, \po, \pt\}$ und sind nicht verändert $\{\po, \po, \pt, \pt\}$
- $\{\po, \pt, \po, \pt\}$ und sind gestört $\{\pt, \po, \pt, \po\}$

Erkundungsanalyse

Ich interessiere mich für die Familie der Multisets mit und für . Insbesondere sei . $n=20$ $n_i=4$ $i\lesssim4$ $\msD=(\gr1^4\,\gr2^4\,\gr3^4\,\gr4^3\,\gr5^2\,\gr6^1\,\gr7^1\,\gr8^1)$

Die Wahrscheinlichkeit , dass zwei zufällige Permutationen und von sind deranged beträgt etwa 3%. $P$ $Q$ $\msD$

Dies kann wie folgt berechnet werden, wobei das te Laguerre-Polynom ist: Siehe hier für eine Erklärung. $L_k$ $k$
$| D D | | S D | p = \int \infty 0 d t e - t \prod i = 1 c L n i (t) = \int \infty 0 d t e - t (L 4 (t)) 3 (L 3 (t)) (L 2 (t)) (L 1 (t)) 3 = 4.5 \times 1011 = n! \prod i = 1 c 1 n i ! = 20 ! ( 4 ! ) 3 ( 3 ! ) ( 2 ! ) ( 1 ! ) 3 = 1.5 \times 1013 = | D D | / | S D | \approx 0.03$ $\begin{align*} \left|{\mathfrak D}_{\msD}\right| &=\int_0^\infty \!\!dt\; e^{-t}\, \prod_{i=1}^c L_{n_i}(t) =\int_0^\infty \!\!dt\; e^{-t}\, \bigl(L_4(t)\bigr)^3\bigl(L_3(t)\bigr)\bigl(L_2(t)\bigr)\bigl(L_1(t)\bigr)^3\\ &=4.5\times10^{11}\\ \left|\mfS_{\msD}\right| &=n!\prod_{i=1}^c \frac1{n_i!} =\frac{20!}{(4!)^3\,(3!)\,(2!)\,(1!)^3} =1.5\times10^{13}\\ p&=\left|{\mathfrak D}_{\msD}\right|/ \left|\mfS_{\msD}\right|\approx0.03\end{align*}$
Die Wahrscheinlichkeit , dass eine zufällige Permutation von ist diffuse beträgt etwa 0,01%, die willkürliche Schwelle bei etwa Einstellung . $P$ $\msD$ $s(P)<25$

Unten ist eine empirische Wahrscheinlichkeitsdarstellung von 100.000 Abtastwerten von wobei eine zufällige Permutation von . $s(P)$ $P$ $\msD$

Bei mittleren Stichprobengrößen . $s(P)\sim \text{Gamma}(\alpha\approx8,\beta\approx18)$

$P {1, 8, 2, 3, 4, 1, 5, 2, 3, 6, 1, 4, 2, 3, 7, 1, 5, 2, 4, 3} {8, 2, 3, 4, 1, 6, 5, 2, 3, 4, 1, 7, 1, 2, 3, 5, 4, 1, 2, 3} {3, 6, 5, 1, 3, 4, 2, 1, 2, 7, 8, 5, 2, 4, 1, 3, 3, 2, 1, 4} {3, 1, 3, 4, 8, 2, 2, 1, 1, 5, 3, 3, 2, 6, 4, 4, 2, 1, 7, 5} {4, 1, 1, 4, 5, 5, 1, 3, 3, 7, 1, 2, 2, 4, 3, 3, 8, 2, 2, 6} s (P) 11 9 \approx 1 140 9 \approx 16 650 9 \approx 72 1223 9 \approx 136 1697 9 \approx 189 cdf (s (P)) < 10 - 5 < 10 - 4 < 1 0.05 < 1 0.45 < 1 0.80$ $\begin{array}{ccl}\renewcommand\mfm[1]{\textbf{#1}} \hline P & s(P) & \text{cdf}(s(P)) \\ \hline \{\po, \ss8, \pt, \pth, \pf, \po, \pv, \pt, \pth, \ss6, \po, \pf, \pt, \pth, \ss7, \po, \pv, \pt, \pf, \pth\} & \frac{11}9\approx1\, & <10^{-5} \\ \{\ss8, \pt, \pth, \pf, \po, \ss6, \pv, \pt, \pth, \pf, \po, \ss7, \po, \pt, \pth, \pv, \pf, \po, \pt, \pth\} & \frac{140}9\approx16 & <10^{-4} \\ \{\pth, \ss6, \pv, \po, \pth, \pf, \pt, \po, \pt, \ss7, \ss8, \pv, \pt, \pf, \po, \pth, \pth, \pt, \po, \pf\} & \frac{650}9\approx72 & \phantom{<1}0.05 \\ \{\pth, \po, \pth, \pf, \ss8, \pt, \pt, \po, \po, \pv, \pth, \pth, \pt, \ss6, \pf, \pf, \pt, \po, \ss7, \pv\} & \frac{1223}9\approx136 & \phantom{<1}0.45 \\ \{\pf, \po, \po, \pf, \pv, \pv, \po, \pth, \pth, \ss7, \po, \pt, \pt, \pf, \pth, \pth, \ss8, \pt, \pt, \ss6\} & \frac{1697}9\approx189 & \phantom{<1}0.80 \\ \hline \end{array}$

Die Wahrscheinlichkeit, dass zwei zufällige Permutationen gültig sind (sowohl diffus als auch gestört), liegt bei . $v\approx(0.03)(0.0001)^2\approx10^{-10}$

Ineffiziente Algorithmen

Ein üblicher "schneller" Algorithmus zum Erzeugen einer zufälligen Störung einer Menge basiert auf Zurückweisung:

do
     P ← zufällige_Permutation ( D )
bis is_derangement ( D , P )
return P

Das dauert ungefähr Iterationen, da es ungefähr mögliche Abweichungen gibt. Ein auf Zurückweisung basierender randomisierter Algorithmus wäre für dieses Problem jedoch nicht effizient, da er Iterationen in der Größenordnung von . $e$ $n!/e$ $1/v\approx10^{10}$

Im Algorithmus von verwendeten Sage , eine zufällige Störung eines multiset „wird durch die Wahl eines Elements nach dem Zufallsprinzip aus der Liste aller möglichen Störungen gebildet.“ Doch auch das ist ineffizient, da es gültige Permutationen, um sie , und außerdem würde man einen Algorithmus brauchen, um das trotzdem zu tun. $v\,|\mfS_{\msD}|^2\approx10^{16}$

Weitere Fragen

Wie komplex ist dieses Problem? Kann es auf ein bekanntes Paradigma wie Netzwerkfluss, Grafikfärbung oder lineare Programmierung reduziert werden?

algorithms combinatorics probability-theory permutations sampling hftf
quelle

Möchtest du in Bezug auf deine Definition von "Spaced Out" nicht, dass für mit als Wächter? Das heißt, ein einzelnes Element sollte sich in der Mitte befinden, zwei sollten die Permutation in Drittel unterteilen und so weiter.

d(i,j)−n/(ni+1) $d(i,j) - n/(n_i + 1)$

0≤i≤j≤n+1 $0 \leq i \leq j \leq n+1$

P0=Pn+1=i $P_0 = P_{n+1} = i$

Raphael

Was passiert, wenn für das Böse (klein, aber groß genug); Haben wir überhaupt diffuse Permutationen als? Wir halten es mit Sicherheit nicht aus, zwei verrückte zu finden! Es scheint, dass kein Element mehr als Mal vorkommen kann.

S={1n−k,2k} $S = \{ 1^{n-k}, 2^k\}$

k $k$

n/2 $n/2$

Raphael

Wie ist das Verhältnis aller Paare gestörter Permutationen unter allen Paaren diffuser Permutationen? Wie viele von allen Paaren gestörter Permutationen bestehen aus zwei diffusen? (Wenn eines der beiden Verhältnisse "hoch" ist, können wir uns auf die eine Hälfte des Prozesses konzentrieren und die andere ablehnen.)

Raphael

@Raphael (# 3a) von 1 Million zufälligen Permutationen von , diese 561 diffus diejenigen hatten . der Paare sind gestört.

D $\mathsf D$

s(P)≤30 $s(P)\le 30$

6118/(5612)=6118/157080≈3.9% $6118/\binom{561}{2}=6118/157080\approx3.9\%$

hftf

@Raphael (# 3b) Von 10 Millionen zufälligen Permutationspaaren von wurden 306893 Paare gestört. Nur 29 dieser Paare hatten beide Permutationen mit . Hier ist ein Histogramm ( Werte ).

D $\mathsf D$

s(P)≤50 $s(P)\le50$

hftf

Antworten:

Ein Ansatz: Sie können dies auf das folgende Problem reduzieren: Wählen Sie bei einer gegebenen Booleschen Formel eine Zuweisung gleichmäßig zufällig aus allen befriedigenden Zuweisungen von . Dieses Problem ist NP-schwer, aber es gibt Standardalgorithmen zum Erzeugen eines , das ungefähr gleichmäßig verteilt ist, und Entlehnungsmethoden aus #SAT-Algorithmen. Zum Beispiel besteht eine Technik darin, eine Hash-Funktion auszuwählen, deren Bereich eine sorgfältig ausgewählte Größe hat (ungefähr dieselbe Größe wie die Anzahl der erfüllenden Zuweisungen von ), und einen Wert innerhalb des Bereichs von gleichmäßig nach dem Zufallsprinzip auszuwählen $\varphi(x)$ $x$ $\varphi(x)$ $x$ $h$ $\varphi$ $y$ $h$ Verwenden Sie dann einen SAT-Löser, um eine zufriedenstellende Zuordnung zu der Formel . Um es effizienter zu gestalten, können Sie als dünne lineare Karte auswählen . $\varphi(x) \land (h(x)=y)$ $h$

Das mag sein, dass Sie einen Floh mit einer Kanone abschießen, aber wenn Sie keine anderen Ansätze haben, die praktikabel erscheinen, können Sie dies versuchen.

DW
quelle

Es fällt mir schwer, dem zu folgen. ist ein Boolescher Wert und ist eine Binärzeichenfolge (eine Menge von Binärvariablen)? Also bedeutet die endgültige Gleichung ...?

$\varphi(x)$

$h(x)$

vzn

Eine ausführliche Diskussion / Analyse dieses Problems begann im cs-Chat mit weiteren Hintergrundinformationen, die eine gewisse Subjektivität in den komplexen Anforderungen des Problems aufdeckten, jedoch keine offensichtlichen Fehler oder Versehen fanden. ¹

Hier ist ein getesteter / analysierter Code, der im Vergleich zu der anderen auf SAT basierenden Lösung relativ "schnell und schmutzig" ist, aber nicht trivial / schwierig zu debuggen war. Es basiert konzeptionell lose auf einem lokalen Pseudozufalls- / Gier-Optimierungsschema, das z. B. 2-OPT für TSP ähnelt . Die Grundidee ist, mit einer zufälligen Lösung zu beginnen, die einer bestimmten Einschränkung entspricht, und sie dann lokal zu stören, um nach Verbesserungen zu suchen, gierig nach Verbesserungen zu suchen und diese zu durchlaufen und zu beenden, wenn alle lokalen Verbesserungen erschöpft sind. Ein Entwurfskriterium war, dass der Algorithmus so effizient wie möglich sein und eine Zurückweisung so weit wie möglich vermeiden sollte.

Es gibt einige Untersuchungen zu Entstellungsalgorithmen [4], die z. B. in SAGE [5] verwendet werden, die sich jedoch nicht an Multisets orientieren.

die einfache Störung ist nur "Vertauschen" von zwei Positionen in dem Tupel (den Tupeln). Die Implementierung ist in Ruby. Es folgen einige Übersichten / Hinweise mit Verweisen auf Zeilennummern.

qb2.rb (gist-github)

Der Ansatz hier ist, mit zwei gestörten Tupeln (# 106) zu beginnen und dann die Dispersion (# 107) lokal / gierig zu verbessern, kombiniert in einem Konzept namens derangesperse(# 97), wobei die Störung erhalten bleibt. Beachten Sie, dass das Vertauschen von zwei gleichen Positionen im Tupelpaar die Störung bewahrt und die Streuung verbessern kann. Dies ist (ein Teil) der Streumethode / -strategie.

Die derangeUnterroutine arbeitet im Array von links nach rechts (Multiset) und tauscht Elemente später im Array aus, wobei der Austausch nicht mit demselben Element erfolgt (# 10). Der Algorithmus ist erfolgreich, wenn die beiden Tupel ohne weitere Auslagerungen an der letzten Position immer noch gestört sind (# 16).

Es gibt drei verschiedene Ansätze, um die anfänglichen Tupel zu verändern. Das 2. Tupel p2wird immer gemischt. man kann mit Tupel 1 ( p1) beginnen, das nach a."höchster Potenz 1. Ordnung" (# 128), b.gemischter Ordnung (# 127) c.und "niedrigster Potenz 1. Ordnung" ("höchster Potenz letzter Ordnung") (# 126) geordnet ist.

Die Dispergierroutine disperseist komplizierter, aber konzeptionell nicht so schwierig. Auch hier werden Swaps verwendet. Anstatt zu versuchen, die Streuung im Allgemeinen über alle Elemente zu optimieren, wird einfach versucht, den aktuell schlimmsten Fall iterativ zu mildern. die Idee ist , die 1 zu finden ^st mindestens disperse Elemente von links nach rechts. Die Störung besteht darin, entweder das linke oder das rechte Element ( x, yIndex) des am wenigsten verteilten Paars mit anderen Elementen zu tauschen, jedoch niemals mit einem anderen zwischen den Paaren (was die Streuung immer verringern würde), und den Versuch zu überspringen, mit denselben Elementen zu tauschen ( selectin # 71). . mist der Mittelpunktindex des Paares (# 65).

Die Streuung wird jedoch über beide Tupel im Paar (Nr. 40) unter Verwendung der "kleinsten / am weitesten links liegenden" Streuung in jedem Paar (Nr. 25, Nr. 44) gemessen / optimiert.

der Algorithmus versucht, swap "hintersten" Elemente 1 ^st ( sort_by / reverse# 71).

Es gibt zwei verschiedene Strategien, true, falseum zu entscheiden, ob das linke oder rechte Element des am wenigsten verteilten Paars (# 80) ausgetauscht werden soll, entweder das linke Element für den Positionswechsel zum linken / rechten Element zur rechten Seite oder das am weitesten links oder rechts gelegene Element im dispersen Paar vom Tauschelement.

Der Algorithmus wird beendet (Nr. 91), wenn die Streuung nicht mehr verbessert werden kann (entweder Verschieben der schlechtesten Streuungsposition nach rechts oder Erhöhen der maximalen Streuung über das gesamte Tupelpaar (Nr. 85)).

Statistiken werden für Ausschuss über c= 1000 Störungen über die 3 Ansätze (# 116) und c= 1000 Störungen (# 97) ausgegeben, wobei die 2 Dispersionsalgorithmen für ein gestörtes Paar von Ausschuss (# 19, # 106) betrachtet werden. Letzteres zeichnet die durchschnittliche Gesamtstreuung (nach garantierter Störung) auf. Ein Beispiellauf ist wie folgt

c       0.661000
b       0.824000
a       0.927000
[2.484, 2, 4]
[2.668, 2, 4]

Dies zeigt, dass der a-trueAlgorithmus die besten Ergebnisse mit ~ 92% Nicht-Zurückweisung und einem durchschnittlichen Abstand der schlechtesten Dispersion von ~ 2,6 und einem garantierten Minimum von 2 über 1000 Versuchen liefert, dh mindestens 1 ungleiches intervenierendes Element zwischen allen Paaren gleicher Elemente. es wurden Lösungen mit bis zu 3 ungleichen intervenierenden Elementen gefunden.

Der Abweichungsalgorithmus ist eine lineare Zeitvorab-Unterdrückung, und der Dispersionsalgorithmus (der bei einer gestörten Eingabe ausgeführt wird) scheint möglicherweise ~ . $O(n \log n)$

¹ Das Problem besteht darin, Quizbowl-Paketanordnungen zu finden, die der sogenannten "Feng-Shui" [1] oder einer "netten" zufälligen Reihenfolge entsprechen, in der "nett" etwas subjektiv und noch nicht "offiziell" quantifiziert ist. Der Autor des Problems hat es auf der Grundlage von Untersuchungen der Quizbowl-Community und "Feng-Shui-Experten" analysiert / auf die Streuungskriterien reduziert. [2] Es gibt verschiedene Ideen zu "Feng-Shui-Regeln". Einige "veröffentlichte" Forschungen wurden zu Algorithmen durchgeführt, sie erscheinen jedoch in einem frühen Stadium. [3]

[1] Packet Feng Shui / QBWiki

[2] Quizbowl-Pakete und Feng Shui / Lifshitz

[3] Frage Placement , HSQuizbowl Resource Center Forum

[4] Random Derangements generieren / Martinez, Panholzer, Prodinger

[5] Sage-Derangement-Algorithmus (Python) / McAndrew

vzn
quelle

Wenn ich weiter darüber nachdenke, gibt es einen Fehler in der derange Routine und es ist nicht immer derange. Die Swap-Position kann vorrücken, ohne etwas zu tauschen. Es gibt eine einfache Lösung, um den Erfolg richtig zu testen.

vzn