Como embaralhar bolas coloridas?

Eu tenho 400 bolas, nas quais 100 são vermelhas, 40 são amarelas, 50 são verdes, 60 são azuis, 70 são roxas, 80 são pretas. (bolas da mesma cor são idênticas)

eu preciso de um algoritmo de embaralhamento eficiente, para que, após embaralhar, as bolas estejam em uma lista e

Quaisquer 3 bolas consecutivas não são da mesma cor. por exemplo, eu não posso ter "vermelho, vermelho, vermelho, amarelo ...."

E toda permutação é "igualmente" provável de ocorrer. (bem, se a troca entre eficiência x imparcialidade é boa o suficiente, não me importo com mais eficiência do que imparcialidade).

Eu tentei adaptar Fisher-Yates-Knuth, mas o resultado não é o ideal.

Por que Fisher-Yates não é bom o suficiente? À medida que o EF adota a transformação inversa de Monte Carlo. E a distribuição de saída trata as bolas da mesma cor de maneira diferente, ou seja, geraria resultado tendencioso para minhas necessidades.

E, o pensamento ingênuo seria filtrar / retroceder todas as permutações ruins de todo o espaço. Quando a restrição é muito forte, digamos, se tivermos apenas 300 bolas e 100 das quais são vermelhas, haverá muitas falhas / rastreamentos nas costas antes de obter uma permutação apropriada.

Então, finalmente, eu gostaria de poder iterar todas as boas permutações. No entanto, como o número de permutações válidas é muito grande, só posso amostrar algumas delas aleatoriamente. Quero que a característica estatística de "alguns" deles se assemelhe à população o máximo possível.

O que você precisa para uma cadeia de Markov convergir para uma distribuição igual em todas as seqüências possíveis de bolas é que ela é reversível: a probabilidade de se mover da sequência para a sequência é a mesma que se mover na direção oposta. Assim, proponho que você use os seguintes movimentos (com alguma distribuição de probabilidade fixa para escolher qual tipo de movimento fazer) para executar uma cadeia de Markov em todas as sequências possíveis. A seguir, uma "corrida" é uma subsequência consecutiva de comprimento máximo de bolas da mesma cor. Essa cadeia de Markov conta com pelo menos três cores.$i$$j$

1. Escolha duas corridas aleatoriamente. Se você puder trocá-los e ainda tiver uma sequência legal, faça-o.

2. Escolha duas pistas adjacentes. Se você puder trocá-los e ainda tiver uma sequência legal, faça-o.

3. Escolha duas corridas da mesma cor. Redistribua as bolas nelas aleatoriamente entre as possibilidades legais (por isso, se o número máximo de bolas em uma única corrida for 3 e você tiver 5 bolas no total nas duas rodadas escolhidas, a primeira provavelmente terá 2 ou 3 bolas; se havia 3 bolas no total, sendo a primeira igualmente igual a 1 ou 2; se houvesse 4 bolas no total, 1, 2 e 3 são igualmente prováveis).

4. Escolha um pouco de cor aleatoriamente. Considere a sequência de bolas com todas as bolas da cor removidas. Agora, escolha aleatoriamente dois pontos em onde as bolas adjacentes de cores diferentes se tocam.$C_i$$S'$$C_i$$S'$

   uma. Se houver duas séries de cores nesses dois pontos na sequência original , e nenhuma tiver comprimento máximo, mova uma bola de uma para a outra, com cada direção escolhida com probabilidade ½.$C_i$$S$

   b. Se houver duas séries de cores nesses dois pontos na sequência original , mas uma tiver comprimento máximo e a outra não, mova a bola do comprimento máximo para a menor com probabilidade ½.$C_i$$S$

   c. Se houver apenas uma sequência de cores em um desses dois pontos em , com probabilidade ½ mova uma bola da sequência para o outro ponto. $C_i$$S$

   d. Se não houver execução da cor em nenhum desses pontos, ou se houver execuções de comprimento máximo em ambos os pontos, não faça nada.$C_i$

Se minha análise estiver correta, é uma cadeia de Markov reversível que eventualmente converge para uma distribuição uniforme de seqüências legais de bolas coloridas; portanto, se você administrar essa cadeia por tempo suficiente, ficará muito próximo dessa distribuição uniforme.

Como você pode saber quando isso convergiu? Eu sugeriria observar a entropia dessa sequência e parar quando ela parar de aumentar. Como você calcula a entropia? Existem dois termos principais no cálculo da entropia: a distribuição dos comprimentos da execução e a sequência de cores que cada execução possui. Para a distribuição dos comprimentos de execução, suponha que haja execuções de cor com comprimento . A contribuição destes para a entropia é onde é o comprimento máximo permitido de uma corrida. Agora, vamos considerar a contribuição da sequência de cores para a entropia. Suponha que haja$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}$locais onde uma sequência de cores é imediatamente seguida por uma de cor (então ). A contribuição disso para a entropia é onde é o número de cores. $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$

(No interesse da precisão, deixe-me observar que estamos deixando de fora uma série de contribuições para a entropia, incluindo a cor da primeira bola, mas esses são termos de ordem inferior que devem ser seguros para negligenciar.)

ATUALIZAR:

Deve haver maneiras de acelerar isso. Acredito que para as etapas c e d, você pode usar a análise para executar essas duas etapas em todas as execuções de uma cor ao mesmo tempo. Para as etapas aeb, isso equivale à questão de encontrar uma sequência aleatória de bolas coloridas com a restrição de que nenhuma das duas bolas da mesma cor toque. Deve haver uma boa maneira de fazer a mixagem para esse problema. Depois, basta alternar as etapas a / b com as etapas c / d, onde cada etapa se mistura completamente com esses dois movimentos. Eu acho que isso deve convergir muito rápido, embora eu não tenha nenhuma análise rigorosa para essa cadeia de Markov.

Como você disse, não é possível garantir que todas as permutações sejam igualmente prováveis e que as cores sejam distribuídas igualmente, porque uma das permutações possui todos os vermelhos seguidos.

Um método muito elegante, mas certamente não óbvio, para garantir a distribuição uniforme das cores é alavancar uma sequência de baixa discrepância.

Suponha que você tenha bolas, numeradas de a e um valor de semente, .$N=400$$1$$N$$s$

Verifique se todas as bolas da mesma cor são numeradas consecutivamente. Ou seja, no seu caso, deixe as primeiras 100 bolas serem vermelhas, as próximas 40 serem amarelas, as próximas 50 verdes, etc.

Em seguida, aloque a bola pelo valor , de modo que: em que$k^{\textrm{th}}$$x_k$

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

• $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$ , a proporção áurea
• o operador que recebe a parte fracionária do argumento$(\textrm{mod} \; 1)$
• $s$ é qualquer valor 'semente' constante que você deseja.

Ou seja, cada uma das bolas receberá um valor de que sempre estará entre 0 e 1.$N$$x_k$

Agora, basta pedir as bolas, em ordem crescente, de acordo com o valor .$x_k$

Por exemplo, usando o valor inicial de , as bolas serão ordenadas da seguinte maneira: $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 \}$$ (onde "$B$"= Azul e" "= preto).$K$

Finalmente, se você deseja coletar uma amostra diferente, basta selecionar um valor de semente diferente, .$s$

O código Python para essa alocação do é o seguinte:$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)