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?

algorithms combinatorics probability-theory permutations sampling 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