Jak tasować kolorowe kulki?

Mam 400 piłek, w których 100 to czerwone, 40 to żółte, 50 to zielone, 60 to niebieskie, 70 to fioletowe, 80 to czarne. (kule tego samego koloru są identyczne)

Potrzebuję wydajnego algorytmu tasowania, aby po tasowaniu kulki znalazły się na liście i

3 kolejne kule nie są tego samego koloru. np. nie mogę mieć „czerwonego, czerwonego, czerwonego, żółtego ....”

I wszystkie permutacje są „jednakowo” prawdopodobne. (cóż, jeśli kompromis między wydajnością a bezstronnością jest wystarczająco dobry, nie mam nic przeciwko większej wydajności niż bezstronności).

Próbowałem przystosować Fishera-Yatesa-Knutha, ale wynik nie jest idealny.

Dlaczego Fisher-Yates nie jest wystarczająco dobry? Gdy FY przyjmuje odwrotną transformację Monte Carlo. A rozkład wyjściowy traktuje te same kolorowe kulki inaczej, tj. Generowałby stronniczy wynik dla moich potrzeb.

Naiwne myślenie polegałoby na odfiltrowaniu / wycofaniu wszystkich złych permutacji z całej przestrzeni. Kiedy ograniczenie jest bardzo silne, powiedzmy, jeśli mamy tylko 300 kulek, z których 100 jest czerwonych, wówczas będzie zbyt wiele śledzenia wstecznego / awarii przed uzyskaniem odpowiedniej permutacji.

Tak więc ostatecznie chciałbym móc iterować przez wszystkie dobre permutacje. Ponieważ jednak liczba prawidłowych permutacji jest zbyt duża, mogę losowo próbkować tylko niektóre z nich. Chcę, aby funkcja statystyczna „niektórych” z nich jak najbardziej przypominała populację.

ds.algorithms randomized-algorithms permutations

— colinfang
źródło

Czy próbowałeś dostosować odpowiedzi z drugiego zadanego pytania ? Oba pytania wyglądają bardzo podobnie :).

— Gopi,

@Gopi: tak i mam nadzieję, że odpowiedzi na jedno pytanie przyniosą inspirację drugiemu.

— colinfang

Najprostszy pomysł, jaki przychodzi mi na myśl, to zacząć losowo wybierać jedną piłkę z jakiegoś koloru, przy czym każdy kolor zostanie wybrany z prawdopodobieństwem opartym na liczbie piłek pozostawionych z tym kolorem, z zastrzeżeniem, że jeśli ostatnie 2 piłki miały tego samego koloru, nie można go wybrać przy bieżącej iteracji. Wydajność nie powinna być zła i nie widzę w tym żadnych stronniczości (co nie znaczy, że jej nie ma; może coś przeoczyłem).

— George,

@George B .: zastanawialiśmy się, dlaczego ten proces ma tendencyjność w stosunku do innego powiązanego pytania. Jak wyjaśnia David Eppstein w swojej odpowiedzi na to pytanie, istnieje algorytm programowania dynamicznego, który zajmuje czas, gdzie jest liczbą kolorów. Przydałoby się coś bardziej wydajnego - nawet .

θ (n^{k})

$\theta(n^k)$

k

$k$

θ (n^{k / 2})

$\theta(n^{k/2})$

— Peter Shor,

@GeorgeB. Nawet jeśli podejście Davida Eppsteina jest tańsze, byłbym zainteresowany sposobem rozwiązania tego problemu za pomocą podejścia MCMC.

— Peter Shor

Odpowiedzi:

To, czego potrzebujesz, aby łańcuch Markowa zbiegał się do równego rozkładu we wszystkich możliwych sekwencjach kul, polega na tym, że jest on odwracalny: prawdopodobieństwo przejścia z sekwencji do sekwencji jest takie samo, jak przejście w przeciwnym kierunku. Proponuję zatem, aby użyć następujących ruchów (z pewnym ustalonym rozkładem prawdopodobieństwa, aby wybrać rodzaj ruchu do wykonania), aby wykonać łańcuch Markowa we wszystkich możliwych sekwencjach. W dalszej części „przebieg” jest kolejną podsekwencją piłek tego samego koloru o maksymalnej długości. Ten łańcuch Markowa opiera się na co najmniej trzech kolorach. $i$ $j$

Wybierz dwa losowe losowania. Jeśli możesz je wymienić i nadal zachować prawidłową kolejność, zrób to.
Wybierz dwa sąsiednie przebiegi. Jeśli możesz je wymienić i nadal zachować prawidłową kolejność, zrób to.
Wybierz dwa przebiegi tego samego koloru. Rozmieść w nich losowo kulki spośród legalnych możliwości (więc jeśli maksymalna liczba piłek w jednym przebiegu wyniosła 3, a ty miałeś łącznie 5 piłek w dwóch wybranych biegach, pierwsza z równym prawdopodobieństwem zdobędzie 2 lub 3 piłki; jeśli w sumie były 3 kule, pierwsza z równym prawdopodobieństwem otrzyma 1 lub 2; jeśli byłyby 4 kule, 1, 2 i 3 są jednakowo prawdopodobne).
Wybierz losowo kolor . Rozważ sekwencję kulek po usunięciu wszystkich kulek koloru . Teraz wybierz losowo dwa punkty w których stykają się sąsiednie kule w różnych kolorach. $C_i$ $S'$ $C_i$ $S'$

za. Jeśli w tych dwóch punktach oryginalnej sekwencji występują dwie serie kolorów żadna z nich nie jest maksymalną długością, przesuń piłkę z jednej na drugą, z każdym kierunkiem wybranym z prawdopodobieństwem ½. $C_i$ $S$

b. Jeśli w tych dwóch punktach oryginalnej sekwencji występują dwa przebiegi koloru , ale jeden ma maksymalną długość, a drugi nie, przesuń piłkę z biegu o maksymalnej długości na krótszy z prawdopodobieństwem ½. $C_i$ $S$

do. Jeśli w jednym z tych dwóch punktów jest tylko jedna seria koloru , z prawdopodobieństwem ½ przenieś jedną piłkę z serii do drugiej. $C_i$ $S$

re. Jeśli w żadnym z tych punktów nie ma serii w obu tych punktach występuje seria o maksymalnej długości, nie rób nic. $C_i$

Jeśli moja analiza jest słuszna, jest to odwracalny łańcuch Markowa, który ostatecznie zbiega się do jednolitego rozkładu legalnych sekwencji kolorowych kulek, więc jeśli uruchomisz ten łańcuch wystarczająco długo, zbliżysz się do tego jednolitego rozkładu.

Jak rozpoznać, kiedy to się zbiegło? Sugerowałbym obserwowanie entropii tej sekwencji i zatrzymanie jej, gdy przestanie rosnąć. Jak obliczyć entropię? Przy obliczaniu entropii istnieją dwa główne terminy: rozkład długości serii i sekwencja kolorów dla każdej serii. Dla rozkładu długości serii załóżmy, że istnieje serii koloru o długości . Wkład z nich do entropii jest $n_{i,k}$ $i$ $k$ gdziejest maksymalną dopuszczalną długością przebiegu. Rozważmy teraz wpływ sekwencji kolorów na entropię. Załóżmy, że istnieją miejscaktórych po seriinastępuje bezpośrednio jeden z kolorów(więc). Wkład ten do entropii jest

\sum_{ja} \log_{2)} (\binom{\sum_{k} n_{ja, k}}{n_{ja, 1} n_{ja, 2)} \dots n_{ja, r}}),

$\sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} },$

r

$r$

m_{i, j}

$m_{i,j}$

i

$i$

j

$j$

m_{i, i} = 0

$m_{i,i}=0$

gdzie

jest liczbą kolorów.

\sum_{ja} \log_{2)} (\binom{\sum_{jot} m_{ja, jot}}{m_{ja, 1} m_{ja, 2)} \dots m_{ja, do}}),

$\sum_i \ \log_2\ { \sum_j m_{i,j} \choose m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} },$

c

$c$

(W trosce o dokładność, proszę zauważyć, że pomijamy szereg wkładów do entropii, w tym kolor pierwszej piłki, ale są to warunki niższego rzędu, które należy bezpiecznie pominąć).

AKTUALIZACJA:

Powinny istnieć sposoby przyspieszenia tego. Uważam, że dla kroków c i d można użyć analizy, aby wykonać oba te kroki dla wszystkich serii jednego koloru jednocześnie. W przypadku etapów aib odpowiada to znalezieniu losowej sekwencji kolorowych kulek z tym ograniczeniem, że nie dotykają się dwie kule tego samego koloru. Powinien istnieć dobry sposób na miksowanie tego problemu. Następnie musisz po prostu zamienić kroki a / b na kroki c / d, gdzie każdy krok całkowicie miesza się z tymi dwoma ruchami. Myślę, że powinno to zbiegać się dość szybko, chociaż nie mam żadnych rygorystycznych analiz dla tego łańcucha Markowa.

— Peter Shor
źródło

Jak już powiedziałeś, nie jest możliwe zapewnienie, że każda permutacja jest jednakowo prawdopodobna i że kolory są równomiernie rozmieszczone, ponieważ jedna z permutacji ma wszystkie czerwone kolory z rzędu.

Bardzo eleganckim, ale z pewnością nieoczywistym sposobem zapewnienia równomiernego rozłożenia kolorów jest wykorzystanie sekwencji o niskiej rozbieżności.

$N=400$ $1$ $N$ $s$

Upewnij się, że wszystkie kule tego samego koloru są kolejno ponumerowane. To znaczy, w twoim przypadku, niech pierwsze 100 piłek będzie czerwonych, następne 40 żółtych, następne 50 zielonych itd.

$k^{\textrm{th}}$ $x_k$

x_{k} = (s + k ϕ) (mod 1),

$x_k = (s+ k \phi) \; (\textrm{mod}\; 1),$

$\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$
$(\textrm{mod} \; 1)$
$s$

$N$ $x_k$

$x_k$

$s=0$

{B, R, K, G, R, P, Y, K, B, R, P, G, K, R, B, Y, K, B, R, P, Y, K, B, R, P, G, R, P, Y, K, B, R, P, G, K, R, B, R, K, G, R, P, Y, K, B, R, P, G, K, R, P, Y, K, B, R, P, G, K, B, R, P, G, R, P, Y, K, B, R, P, G, K, R, B, R, K, G, R, P, Y, K, B, R, P, G, K, R, P, Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, b, Y, K., b, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, P., Y, K., b, R, P., sol, K., b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, b, Y, K., sol, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, b, Y, K., b, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, b, Y, K., b, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, P., Y, K., b, R, P., sol, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, b, Y, K., b, R, P., Y, K., b, R, P., sol, R, P., Y, K., b, R, P., sol, K., R, b, R, K., sol, R, P., Y, K., b, R, P., sol, K., R, P., Y, K., b, R, P., sol, K.}

$\{B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,G,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K \}$

B

$B$

K

$K$

$s$

$x_k$

n=400

phi = (1+pow(5,0.5))/2
x = np.zeros(n)                 
s = np.random.uniform(0,1)
for i in range(n):
    x = (s + phi*(i+1)) %1

print (s)
print (x)

— Martin Roberts
źródło