Как перемешать цветные шарики?

У меня есть 400 шаров, из которых 100 - красные, 40 - желтые, 50 - зеленые, 60 - синие, 70 - фиолетовые, 80 - черные. (шарики одного цвета идентичны)

мне нужен эффективный алгоритм перетасовки, чтобы после перетасовки шары были в списке, и

Любые 3 последовательных шара не одного цвета. Например, я не могу иметь "красный, красный, красный, желтый ...."

И все перестановки "одинаково" могут произойти. (хорошо, если компромисс между эффективностью и непредвзятостью достаточно хорош, я не против большей эффективности, чем объективность).

Я пытался приспособить Фишера-Йейтса-Кнута, но результат не идеален.

Почему Фишер-Йейтс недостаточно хорош? Как FY принимает обратное преобразование Монте-Карло. А выходной дистрибутив обрабатывает шары одного цвета по-разному, то есть он будет давать смещенный результат для моих нужд.

И наивное мышление должно было бы отфильтровать / отследить все плохие перестановки из всего пространства. Когда ограничение очень сильное, скажем, если у нас есть только 300 шаров, из которых 100 красных, то будет слишком много отслеживания / отказов назад, прежде чем получить соответствующую перестановку.

Итак, в конечном счете, я хотел бы иметь возможность перебирать все хорошие перестановки. Однако, поскольку число допустимых перестановок слишком велико, я могу только случайным образом отобрать некоторые из них. Я хочу, чтобы статистические особенности "некоторых" из них максимально напоминали население.

То, что вам нужно, чтобы цепь Маркова сходилась к равному распределению по всем возможным последовательностям шаров, - это то, что она обратима: вероятность перехода из последовательности в последовательность j такая же, как и движение в противоположном направлении. Поэтому я предлагаю вам использовать следующие ходы (с некоторым фиксированным распределением вероятностей, чтобы выбрать, какой тип хода сделать), чтобы выполнить цепочку Маркова на всех возможных последовательностях. В последующем «пробег» - это последовательная последовательность максимальной длины шаров одного цвета. Эта цепь Маркова опирается на наличие как минимум трех цветов.$i$$j$

1. Выберите два прогона наугад. Если вы можете обменять их и все еще иметь юридическую последовательность, сделайте это.

2. Выберите две соседние трассы. Если вы можете обменять их и все еще иметь юридическую последовательность, сделайте это.

3. Выберите две серии одного цвета. Перераспределите шары в них случайным образом среди легальных возможностей (поэтому, если максимальное количество шаров в одном заезде было 3, и у вас было всего 5 шаров в двух выбранных заездах, первый из них с равной вероятностью получит 2 или 3 шара; если всего было 3 мяча, первый с равной вероятностью получит 1 или 2; если было всего 4 мяча, 1, 2 и 3 одинаково вероятны).

4. Выберите цвет наугад. Рассмотрим последовательность шаров S ′ со всеми удаленными шарами цвета C i . Теперь выберите случайным образом две точки в S ′, где соприкасаются смежные шары разных цветов.$C_i$$S'$$C_i$$S'$

   а. Если в этих двух точках в исходной последовательности S есть две серии цветов , и ни одна из них не является максимальной длиной, переместите шар из одной в другую, причем каждое направление выбирается с вероятностью 1/2.$C_i$$S$

   б. Если в этих двух точках в исходной последовательности S есть две серии цветов , но одна имеет максимальную длину, а другая - нет, переместите шарик с максимальной длины на более короткую с вероятностью ½.$C_i$$S$

   с. Если в одной из этих двух точек в S есть только одна пробежка цвета , с вероятностью ½ переместите один мяч из пробега в другую точку. $C_i$$S$

   д. Если в одной из этих точек нет трассы цвета или если в обеих этих точках есть трассы максимальной длины, ничего не делайте.$C_i$

Если мой анализ верен, то это обратимая цепочка Маркова, которая в конечном итоге сходится к равномерному распределению законных последовательностей цветных шаров, поэтому, если вы запустите эту цепочку достаточно долго, вы очень приблизитесь к этому равномерному распределению.

Как вы можете сказать, когда это сошлось? Я бы предложил посмотреть энтропию этой последовательности и остановиться, когда она перестанет расти. Как вы вычисляете энтропию? В вычислении энтропии есть два основных термина: распределение длин серий и последовательность цветов каждого цикла. Для распределения длин серий предположим, что существует трасс цвета i с длиной k . Вклад их в энтропию ∑ i log 2 ( ∑ k n i , $n_{i,k}$$i$$k$ где- максимально допустимая длина серии. Теперь рассмотрим вклад цветовой последовательности в энтропию. Предположим, что естьмест, где сразу за серией цветовследует один из цветов(поэтому). Вклад в энтропию: где- количество цветов.

$$\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$ $$\sum_i \ \log_2\ { \sum_j m_{i,j} \choose m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} },$$ $c$

(В целях точности позвольте мне отметить, что мы упускаем ряд вкладов в энтропию, включая цвет первого шара, но это члены более низкого порядка, которыми следует пренебрегать.)

ОБНОВИТЬ:

Должны быть способы ускорить это. Я полагаю, что для шагов c и d вы можете использовать анализ, чтобы выполнить оба этих шага для всех прогонов одного цвета одновременно. Для шагов a и b это эквивалентно вопросу о нахождении случайной последовательности цветных шариков с условием, что никакие два шарика одного цвета не соприкасаются. Там должен быть какой-то хороший способ сделать смешивание для этой проблемы. Тогда вам просто нужно чередовать шаги a / b с шагами c / d, где каждый шаг полностью смешивается с этими двумя шагами. Я думаю, что это должно сходиться довольно быстро, хотя у меня нет строгого анализа для этой цепи Маркова.

Как вы сказали, невозможно гарантировать, что каждая перестановка одинаково вероятна, и обеспечить равномерное распределение цветов, потому что одна из перестановок имеет все красные в ряду.

Очень элегантный, но, безусловно, неочевидный метод обеспечения равномерного распределения цветов состоит в использовании последовательности с малым расхождением.

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

Убедитесь, что все шарики одного цвета последовательно пронумерованы. То есть, в вашем случае, пусть первые 100 шаров будут красными, следующие 40 будут желтыми, следующие 50 зелеными и т. Д.

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

То есть каждому из шаров будет присвоено значение которое всегда будет между 0 и 1.$N$$x_k$

Теперь просто упорядочите шары в порядке возрастания в соответствии с их значением .$x_k$

Например, используя начальное значение , шары будут упорядочены следующим образом: $s=0$B

$$\{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$

Код Python для этого выделения выглядит следующим образом:$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)