Comment mélanger les boules de couleur?

J'ai 400 balles, dont 100 rouges, 40 jaunes, 50 vertes, 60 bleues, 70 violettes, 80 noires. (les boules de la même couleur sont identiques)

j'ai besoin d'un algorithme de brassage efficace, de sorte qu'après le brassage, les balles soient dans une liste, et

Les 3 balles consécutives ne sont pas de la même couleur. par exemple, je ne peux pas avoir "rouge, rouge, rouge, jaune ...."

Et, toutes les permutations sont "également" susceptibles de se produire. (eh bien, si le compromis entre l'efficacité et l'impartialité est assez bon, cela ne me dérange pas plus d'efficacité que l'impartialité).

j'ai essayé d'adapter Fisher-Yates-Knuth, mais le résultat n'est pas idéal.

Pourquoi Fisher-Yates n'est pas assez bon? Comme FY adopte la transformation inverse de Monte Carlo. Et la distribution de sortie traite les mêmes boules de couleur différemment, c'est-à-dire qu'elle générerait un résultat biaisé pour mes besoins.

Et, la pensée naïve serait de filtrer / reculer toutes les mauvaises permutations de tout l'espace. Lorsque la restriction est très forte, disons, si nous n'avons que 300 balles et 100 d'entre elles sont rouges, alors il y aura trop de back tracking / échecs avant d'obtenir une permutation appropriée.

Donc, en fin de compte, je souhaiterais pouvoir parcourir toutes les bonnes permutations. Cependant, comme le nombre de permutations valides est trop important, je ne peux en échantillonner que de manière aléatoire. Je veux que la caractéristique statistique de "certains" d'entre eux ressemble autant que possible à la population.

$i$$j$

1. Choisissez deux pistes au hasard. Si vous pouvez les échanger et avoir encore une séquence légale, faites-le.

2. Choisissez deux pistes adjacentes. Si vous pouvez les échanger et avoir encore une séquence légale, faites-le.

3. Choisissez deux séries de la même couleur. Redistribuez les balles au hasard parmi les possibilités légales (donc si le nombre maximum de balles dans une même manche était de 3, et que vous aviez 5 balles au total dans les deux pistes choisies, la première est également susceptible d'obtenir 2 ou 3 balles; si il y avait 3 boules au total, la première est également susceptible d'obtenir 1 ou 2; s'il y avait 4 boules au total, 1, 2 et 3 sont toutes également susceptibles).

4. $C_i$$S'$$C_i$$S'$

   $C_i$$S$

   $C_i$$S$

   $C_i$$S$

   $C_i$

Si mon analyse est juste, il s'agit d'une chaîne de Markov réversible qui converge finalement vers une distribution uniforme de séquences légales de boules colorées, donc si vous exécutez cette chaîne assez longtemps, vous vous rapprocherez très près de cette distribution uniforme.

$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}$ endroits où une suite de couleur est immédiatement suivie par une de couleur (donc ). La contribution de ceci à l'entropie est où est le nombre de couleurs. $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$

(Dans un souci d'exactitude, permettez-moi de noter que nous omettons un certain nombre de contributions à l'entropie, y compris la couleur de la première balle, mais ce sont des termes d'ordre inférieur qui doivent être négligés.)

MISE À JOUR:

Il devrait y avoir des moyens d'accélérer cela. Je crois que pour les étapes c et d, vous pouvez utiliser l'analyse pour effectuer ces deux étapes sur tous les cycles d'une seule couleur à la fois. Pour les étapes a et b, cela équivaut à la question de trouver une séquence aléatoire de boules colorées avec la contrainte qu'aucune boule de la même couleur ne se touche. Il devrait y avoir un bon moyen de faire le mixage pour ce problème. Ensuite, il vous suffit d'alterner les étapes a / b avec les étapes c / d, où chaque étape se mélange complètement à ces deux mouvements. Je pense que cela devrait converger assez rapidement, même si je n'ai pas d'analyse rigoureuse pour cette chaîne de Markov.

Comme vous l'avez dit, il n'est pas possible de garantir que chaque permutation est également probable et de s'assurer que les couleurs sont réparties uniformément, car l'une des permutations a tous les rouges d'affilée.

Une méthode très élégante, mais certainement pas évidente, pour assurer une répartition uniforme des couleurs consiste à tirer parti d'une séquence à faible écart.

Supposons que vous ayez boules, numérotées de à , et une valeur de départ, .$N=400$$1$$N$$s$

Assurez-vous que toutes les boules de la même couleur sont numérotées consécutivement. C'est-à-dire, dans votre cas, que les 100 premières boules soient rouges, les 40 prochaines jaunes, les 50 prochaines vertes, etc.

Ensuite, allouez à la boule la valeur, telle que: où$k^{\textrm{th}}$$x_k$

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

• $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$ , le nombre d'or
• l' opérateur qui prend la partie fractionnaire de l'argument$(\textrm{mod} \; 1)$
• $s$ est toute valeur de «graine» constante que vous souhaitez.

Autrement dit, chacune des boules se verra attribuer une valeur de qui sera toujours comprise entre 0 et 1.$N$$x_k$

Maintenant, commandez simplement les boules, dans l'ordre croissant en fonction de leur valeur .$x_k$

Par exemple, en utilisant la valeur de départ de , les boules seront ordonnées comme suit: $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 \}$$ (où "$B$"= Bleu et" "= Noir).$K$

Enfin, si vous souhaitez prélever un échantillon différent, sélectionnez simplement une valeur de graine différente, .$s$

Le code Python pour cette allocation de est le suivant:$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)