Wydajny algorytm do generowania losowo dwóch rozproszonych, obłąkanych permutacji multiset

tło

$\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$ Załóżmy, że mam dwie identyczne partie $n$ kulek. Każdy marmur może mieć jeden z kolorów $c$ , gdzie $c≤n$ . Niech $n_i$ oznacza liczbę kulek koloru $i$ w każdej partii.

Niech $\msS$ będzie $\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\}$ reprezentujący jedną partię. W reprezentacji częstotliwości , $\msS$ może być zapisany jako $(\po^{n_1} \;\pt^{n_2}\; … \;\pc^{n_c})$ .

Liczbę różnych $\msS$ podaje wielomian :

| S_{S} | = (\binom{n}{n_{1}, n_{2}, \dots, n_{c}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{c}!} = n! \prod_{i = 1}^{c} \frac{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!}.$

Pytanie

Czy istnieje skuteczny algorytm do generowania losowo dwóch rozproszonych, zaburzonych permutacji $P$ i $Q$ dla $\msS$ ? (Rozkład powinien być jednolity.)

Permutacja $P$ jest rozproszony w przypadku każdego odrębnego elementu $i$ z $P$ , przypadki $i$ są rozmieszczone w przybliżeniu równomiernie $P$ .
Załóżmy na przykład, że $\msS=(\po^4\;\pt^4)=\{\po,\po,\po,\po,\pt,\pt,\pt,\pt\}$ .
- $\{\po, \po, \po, \pt, \pt, \pt, \pt, \po\}$ nie jest rozproszony
- $\{\po, \pt, \po, \pt, \po, \pt, \po, \pt\}$ jest rozproszony
Bardziej rygorystycznie:
- Jeśli , istnieje tylko jedno wystąpienie do „spacji” w , więc niech . $n_i=1$ $i$ $P$ $\Delta(i)=0$
- Inaczej, niech jest odległością pomiędzy przykład a przykład w w . Odejmij od niego oczekiwaną odległość między instancjami , definiując następujące elementy: Jeśli jest równomiernie rozmieszczone w , to powinna wynosić zero lub być bardzo bliska zeru, jeśli . $d(i,j)$ $j$ $j+1$ $i$ $P$ $i$ $δ (i, j) = d (i, j) - \frac{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$ $i$ $P$ $\Delta(i)$ $n_i\nmid n$
Teraz określić statystycznego do zmierzenia ile każda równomiernie rozstawione w . Nazywamy rozpraszanie jeśli jest bliskie zeru lub z grubsza . (Można wybrać próg specyficzny dla , aby było rozproszone, jeśli ) $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$

To ograniczenie przywołuje bardziej rygorystyczny problem planowania w czasie rzeczywistym, zwany problemem pinwheel z multiset (tak, że ) i gęstością . Celem jest zaplanowanie cyklicznej nieskończonej sekwencji tak, aby każda podsekwencja o długości zawierała co najmniej jedno wystąpienie . Innymi słowy, wykonalny harmonogram wymaga wszystkich ; Jeśli gęsta ( ), a i . Problem z mechanizmem Wiatraczek wydaje się być NP-zupełny. $\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$
Dwa permutacji i są niezrównoważoną jeśli jest derangement z ; to znaczy dla każdego indeksu . $P$ $Q$ $P$ $Q$ $P_i ≠ Q_i$ $i\in[n]$
Załóżmy na przykład, że . $\msS=(\po^2\;\pt^2)=\{\po,\po,\pt,\pt\}$
- $\{\po, \pt, \po, \pt\}$ i nie są zaburzone $\{\po, \po, \pt, \pt\}$
- $\{\po, \pt, \po, \pt\}$ i są zaburzone $\{\pt, \po, \pt, \po\}$

Analiza eksploracyjna

Interesuje mnie rodzina multisets o i dla . W szczególności niech . $n=20$ $n_i=4$ $i\lesssim4$ $\msD=(\gr1^4\,\gr2^4\,\gr3^4\,\gr4^3\,\gr5^2\,\gr6^1\,\gr7^1\,\gr8^1)$

Prawdopodobieństwo, że dwie losowe permutacji i o są niezrównoważoną około 3%. $P$ $Q$ $\msD$

Można to obliczyć w następujący sposób, gdzie jest tym wielomianem Laguerre'a: Patrz tutaj dla wyjaśnienia. $L_k$ $k$
$\begin{aligned} | D_{D} | & = \int_{0}^{\infty} d t e^{- t} \prod_{i = 1}^{c} L_{n_{i}} (t) = \int_{0}^{\infty} d t e^{- t} (L_{4} (t))^{3} (L_{3} (t)) (L_{2} (t)) (L_{1} (t))^{3} \\ = 4.5 \times 10^{11} \\ | S_{D} | & = n! \prod_{i = 1}^{c} \frac{1}{n_{i}!} = \frac{20!}{(4!)^{3} (3!) (2!) (1!)^{3}} = 1.5 \times 10^{13} \\ p & = | D_{D} | / | S_{D} | \approx 0.03 \end{aligned}$ $\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*}$
Prawdopodobieństwo, że bezładny permutacji o jest rozproszony ustawienie dowolnego progu w przybliżeniu wynosi 0,01%, . $P$ $\msD$ $s(P)<25$

Poniżej znajduje się empiryczny wykres prawdopodobieństwa 100 000 próbek gdzie jest permutacją losową . $s(P)$ $P$ $\msD$

Przy średnich rozmiarach próbek . $s(P)\sim \text{Gamma}(\alpha\approx8,\beta\approx18)$

$\begin{array}{ccl} P & s (P) & cdf (s (P)) \\ {1, 8, 2, 3, 4, 1, 5, 2, 3, 6, 1, 4, 2, 3, 7, 1, 5, 2, 4, 3} & \frac{11}{9} \approx 1 & < 10^{- 5} \\ {8, 2, 3, 4, 1, 6, 5, 2, 3, 4, 1, 7, 1, 2, 3, 5, 4, 1, 2, 3} & \frac{140}{9} \approx 16 & < 10^{- 4} \\ {3, 6, 5, 1, 3, 4, 2, 1, 2, 7, 8, 5, 2, 4, 1, 3, 3, 2, 1, 4} & \frac{650}{9} \approx 72 & 0.05 \\ {3, 1, 3, 4, 8, 2, 2, 1, 1, 5, 3, 3, 2, 6, 4, 4, 2, 1, 7, 5} & \frac{1223}{9} \approx 136 & 0.45 \\ {4, 1, 1, 4, 5, 5, 1, 3, 3, 7, 1, 2, 2, 4, 3, 3, 8, 2, 2, 6} & \frac{1697}{9} \approx 189 & 0.80 \end{array}$ $\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}$

Prawdopodobieństwo, że dwie losowe kombinacje są prawidłowe (zarówno rozproszone, jak i zaburzone) wynosi około . $v\approx(0.03)(0.0001)^2\approx10^{-10}$

Nieefektywne algorytmy

Popularny algorytm „szybki” do generowania przypadkowego zaburzenia zestawu jest oparty na odrzuceniu:

do
     P ← random_permutation ( D )
do momentu wymowy ( D , P )
zwróć P

która zajmuje około iteracji, ponieważ istnieje mniej możliwe zaburzeniami. Jednak algorytm losowy oparty na odrzuceniu nie byłby skuteczny w przypadku tego problemu, ponieważ przyjmowałby on kolejność iteracji. $e$ $n!/e$ $1/v\approx10^{10}$

W algorytmie stosowanym przez Sage'a przypadkowe wykolejenie zbioru wielokrotnego „powstaje poprzez wybranie losowego elementu z listy wszystkich możliwych odchyleń”. Jednak to również jest nieefektywne, ponieważ istnieją prawidłowe permutacje do wyliczenia, a poza tym do zrobienia tego potrzebny byłby algorytm. $v\,|\mfS_{\msD}|^2\approx10^{16}$

Dalsze pytania

Jaka jest złożoność tego problemu? Czy można go sprowadzić do dowolnego znanego paradygmatu, takiego jak przepływ sieci, kolorowanie wykresów lub programowanie liniowe?

— hftf
źródło

Jeśli chodzi o twoją definicję „odstępów”, nie chcesz, aby dla z jako wartownicy? Innymi słowy, pojedynczy element powinien znajdować się na środku, dwa powinny podzielić permutację na trzy części i tak dalej.

d (i, j) - n / (n_{i} + 1)

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

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

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

P_{0} = P_{n + 1} = i

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

— Raphael

Co się stanie, jeśli dla zła (małe, ale wystarczająco duże); możemy nawet mieć rozproszonych permutacje niż? Z pewnością nie znosimy zmiany, by znaleźć dwóch obłąkanych! Wydaje się, że żaden element nie może wystąpić więcej niż razy.

S = {1^{n - k}, 2^{k}}

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

k

$k$

n / 2

$n/2$

— Raphael

Jaki jest stosunek wszystkich par permutacji zaburzonych między wszystkimi parami permutacji rozproszonych ? Podobnie, spośród wszystkich par obłąkanych permutacji, ile składa się z dwóch rozproszonych? (Jeśli którykolwiek z tych współczynników jest „wysoki”, możemy skoncentrować nasz wysiłek na jednej połowie procesu, pozostawiając drugą na odrzuceniu.)

— Raphael

@Raphael (# 3a) Z 1 miliona losowych permutacji , 561 rozproszonych miało . par jest zaburzonych.

D

$\mathsf D$

s (P) \leq 30

$s(P)\le 30$

6118 / (\binom{561}{2}) = 6118 / 157080 \approx 3.9 %

$6118/\binom{561}{2}=6118/157080\approx3.9\%$

— hftf

@Raphael (# 3b) Z 10 milionów losowych par permutacji , 306893 par zostało zaburzonych. Tylko 29 z tych par miało obie permutacje z . Oto histogram ( wartości ).

D

$\mathsf D$

s (P) \leq 50

$s(P)\le50$

— hftf

Odpowiedzi:

Jedno podejście: możesz zredukować to do następującego problemu: Biorąc pod uwagę formułę logiczną , wybierz losowo przypisanie równomiernie spośród wszystkich zadowalających przypisań . Problem ten jest trudny dla NP, ale istnieją standardowe algorytmy do generowania który jest w przybliżeniu równomiernie rozmieszczony, zapożyczając metody z algorytmów #SAT. Na przykład jedną z technik jest wybranie funkcji skrótu której zakres ma starannie wybrany rozmiar (mniej więcej taki sam rozmiar, jak liczba spełniających przypisań ), losowo wybrać równomiernie wartość z zakresu $\varphi(x)$ $x$ $\varphi(x)$ $x$ $h$ $\varphi$ $y$ $h$ , a następnie użyj solwera SAT, aby znaleźć satysfakcjonujące przypisanie do formuły . Aby uczynić go wydajnym, możesz wybrać jako rzadką mapę liniową. $\varphi(x) \land (h(x)=y)$ $h$

Może to być strzelanie do pchły za pomocą armaty, ale jeśli nie masz innych podejść, które wydają się wykonalne, możesz spróbować.

— DW
źródło

jest to trudne do naśladowania. jest wartością logiczną, a jest łańcuchem binarnym (zestaw zmiennych binarnych)? więc końcowe równanie oznacza ...?

φ (x)

$\varphi(x)$

h (x)

$h(x)$

— 2015 r

pogłębiona dyskusja / analiza tego problemu rozpoczęła się na czacie cs z dalszym tłem, które ujawniło pewną subiektywność w złożonych wymaganiach problemu, ale nie znalazło żadnych bezpośrednich błędów ani przeoczeń. ¹

oto trochę przetestowanego / przeanalizowanego kodu, który w porównaniu z innym rozwiązaniem opartym na SAT jest stosunkowo „szybki i brudny”, ale nie był łatwy do debugowania. jest luźno koncepcyjnie oparty na lokalnym pseudolosowym / chciwym schemacie optymalizacji nieco podobnym do np. 2-OPT dla TSP . podstawową ideą jest rozpoczęcie od losowego rozwiązania, które pasuje do pewnego ograniczenia, a następnie zakłócenie go lokalnie, aby szukać ulepszeń, zachłannie szukając ulepszeń i iteracji przez nie, i kończąc, gdy wszystkie lokalne ulepszenia zostaną wyczerpane. Kryterium projektowe było takie, że algorytm powinien być tak wydajny / unikać odrzucenia, jak to tylko możliwe.

istnieją badania nad algorytmami derangancji [4], np. stosowanymi w SAGE [5], ale nie są one zorientowane na multisety.

prosta perturbacja to „zamiana” tylko dwóch pozycji w krotce (-ach). implementacja jest w rubinie. poniżej znajduje się przegląd / uwagi z odniesieniami do numerów linii.

qb2.rb (gist-github)

podejście tutaj polega na tym, aby zacząć od dwóch niepoprawnych krotek (# 106), a następnie lokalnie / łapczywie poprawić rozproszenie (# 107), połączone w koncepcji zwanej derangesperse(# 97), zachowując odstępstwo. zwróć uwagę, że zamiana dwóch takich samych pozycji w parze krotek pozwala zachować odstępstwo i może poprawić dyspersję oraz że jest to (część) metoda / strategia rozproszenia.

derangepodprogram działa od lewej do prawej na tablicy (multiset) i swapów z elementami później w tablicy gdzie swap nie jest z tego samego elementu (# 10). algorytm się powiedzie, jeśli bez dalszych zamian na ostatniej pozycji dwa krotki nadal są zaburzone (# 16).

istnieją 3 różne podejścia do zmniejszania początkowych krotek. 2. krotka p2jest zawsze tasowana. można zacząć od krotki 1 ( p1) uporządkowanej według a.„najwyższych mocy 1. rzędu” (# 128), b.kolejności losowej (nr 127) c.i „najniższych mocy 1. rzędu” („najwyższe moce ostatniego rzędu”) (# 126).

procedura rozproszenia dispersejest bardziej zaangażowana, ale koncepcyjnie nie jest tak trudna. znowu używa swapów. zamiast ogólnie optymalizować dyspersję wszystkich elementów, po prostu próbuje iteracyjnie złagodzić obecny najgorszy przypadek. chodzi o to, aby znaleźć 1 ^st elementy najmniej rozproszyć, od lewej do prawej. zaburzenie polega na zamianie lewego lub prawego elementu ( x, yindeksów) najmniej rozproszonej pary z innymi elementami, ale nigdy żadnej z pary (co zawsze zmniejszałoby dyspersję), a także pomijanie próby zamiany z tymi samymi elementami ( selectw # 71) . mjest indeksem punktu środkowego pary (# 65).

jednak dyspersja jest mierzona / optymalizowana dla obu krotek w parze (# 40) przy użyciu dyspersji „najmniej / najbardziej na lewo” w każdej parze (# 25, # 44).

algorytm próbuje zamienić „najdalsze” elementy 1 ^st ( sort_by / reverse# 71).

istnieją dwie różne strategie true, falsedecydowania, czy zamienić lewy czy prawy element najmniej rozproszonej pary (# 80), albo lewy element do zamiany pozycji na lewy / prawy element na prawą stronę, albo najdalszy lewy lub prawy element w parze rozproszonej od elementu wymiany.

algorytm kończy się (# 91), gdy nie jest już w stanie poprawić dyspersji (albo przesuwa najgorsze miejsce rozproszenia w prawo, albo zwiększa maksymalną dyspersję w całej parze krotek (# 85)).

statystyki są wyprowadzane dla odrzutów powyżej c= 1000 derangencji w 3 podejściach (# 116) i c= 1000 derangesperses (# 97), patrząc na 2 algorytmy rozproszone dla obłąkanej pary od odrzucenia (# 19, # 106). ten ostatni śledzi całkowite średnie rozproszenie (po gwarantowanym zaburzeniu). przykładowy przebieg jest następujący

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

pokazuje to, że a-truealgorytm daje najlepsze wyniki przy ~ 92% braku odrzucenia i średniej najgorszej odległości rozproszenia ~ 2,6 oraz gwarantowanym minimum 2 z ponad 1000 prób, tj. co najmniej 1 nierównomiernym elementem pośredniczącym między wszystkimi parami tego samego elementu. znalazł rozwiązania aż 3 nierównomierne elementy.

algorytm derangencji jest liniowym wstępnym odrzuceniem czasu, a algorytm dyspersji (działający na zmienionym wejściu) wydaje się być prawdopodobnie ~ . $O(n \log n)$

¹ problemem jest znalezienie aranżacji pakietów quizbowl, które spełniają tak zwane „feng shui” [1] lub „ładne” losowe porządkowanie, w którym „miły” jest nieco subiektywny i nie jest jeszcze „oficjalnie” skwantyfikowany; autor problemu przeanalizował / sprowadził go do kryteriów obłąkania / rozproszenia na podstawie badań społeczności quizbowl i „ekspertów feng shui” [2]. istnieją różne pomysły na „zasady feng shui”. przeprowadzono pewne „opublikowane” badania nad algorytmami, ale pojawiają się one we wczesnych stadiach. [3]

[1] Pakiet feng shui / QBWiki

[2] Pakiety Quizbowl i feng shui / Lifshitz

[3] Umieszczanie pytań , forum centrum zasobów HSQuizbowl

[4] Generowanie losowych błędów / Martinez, Panholzer, Prodinger

[5] Algorytm deratyzacji mędrca (python) / McAndrew

— vzn
źródło

fyi dalej myślałem, że jest usterka w szaleńczej rutynie i to nie zawsze szaleje. pozycja wymiany może się zmieniać bez zamiany czegokolwiek. istnieje prosta poprawka do poprawnego przetestowania sukcesu.

— vzn