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ę.

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 j 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$

1. Wybierz dwa losowe losowania. Jeśli możesz je wymienić i nadal zachować prawidłową kolejność, zrób to.

2. Wybierz dwa sąsiednie przebiegi. Jeśli możesz je wymienić i nadal zachować prawidłową kolejność, zrób to.

3. 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).

4. Wybierz losowo kolor . Rozważ sekwencję S ′ kulek po usunięciu wszystkich kulek koloru C i . Teraz wybierz losowo dwa punkty w S ′, 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 S 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 S 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 S 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 i o długości k . Wkład z nich do entropii jest Σ i log 2 ( Σ k n i , $n_{i,k}$$i$$k$ gdzierjest maksymalną dopuszczalną długością przebiegu. Rozważmy teraz wpływ sekwencji kolorów na entropię. Załóżmy, że istnieją miejscami,j, poktórych po seriiinastępuje bezpośrednio jeden z kolorówj(więcmi,i=0). Wkład ten do entropii jest Σilog2(Σj

$$\sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} },$$ $r$$m_{i,j}$$i$$j$$m_{i,i}=0$ gdziecjest liczbą kolorów. $$\sum_i \ \log_2\ { \sum_j m_{i,j} \choose m_{i,1}\ m_{i,2}\ \ldots \ m_{i,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.

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 \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,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$$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)