10
$\begingroup$

I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical)

i need an efficient shuffling algorithm, so that after shuffling, balls are in a list, and

Any consecutive 3 balls are not of the same colour. e.g, i can not have "red, red, red, yellow...."

And, all permutation are "equally" likely to occur. (well, if the trade-off of efficiency vs. unbiasedness is good enough, i don't mind more efficiency than unbiasedness).

i tried to adapt Fisher-Yates-Knuth, but the outcome is not ideal.

Why Fisher-Yates not good enough? As FY adopts Monte Carlo inverse transformation. And the output distribution treats the same colour balls differently, i.e. it would generate biased result for my needs.

And, the Naive thinking would be to filter out / backtracking all bad permutations from the whole space. When the restriction is very strong, say, if we have only 300 balls and 100 of which are red, then there will be too many back tracking/failures before getting an appropriate permutation.

So, ultimately, I would wish to be able to iterate through all good permutations. However, because the number of valid permutations is too large, i can only randomly sample some of them. I wanna the statistical feature of the "some" of them resemble the population as much as possible.

$\endgroup$
  • 3
    $\begingroup$ Have you tried to adapt the answers from the other question you asked? Both questions look very similar :). $\endgroup$ – Gopi Oct 23 '11 at 9:53
  • $\begingroup$ @Gopi: yes, and i hope the answers for either question would bring inspiration to the other. $\endgroup$ – colinfang Oct 23 '11 at 10:06
  • $\begingroup$ The simplest idea that comes to my mind is to start choosing randomly one ball from some color, where each color will be chosen with a probability based on the number of balls left with that color, with the restriction that if the last 2 balls had the same color, you cannot choose it at the current iteration. The efficiency shouldn't be bad and I can't see any bias in it (which doesn't mean that there is none; maybe I miss something). $\endgroup$ – George Oct 23 '11 at 10:22
  • 3
    $\begingroup$ @George B.: we went through why this process does have bias on the other related question. As David Eppstein explains in his answer to that question, there's a dynamic programming algorithm that takes $\theta(n^k)$ time, where $k$ is the number of colors. Something more efficient would be nice--even $\theta(n^{k/2})$. $\endgroup$ – Peter Shor Oct 23 '11 at 13:17
  • 2
    $\begingroup$ @GeorgeB. Even if David Eppstein's approach is cheaper, I'd be interested in how to solve this problem with a MCMC approach. $\endgroup$ – Peter Shor Oct 24 '11 at 12:40
7
$\begingroup$

What you need for a Markov chain to converge to an equal distribution over all possible sequences of balls is that it is reversible: the probability of moving from sequence $i$ to sequence $j$ is the same as moving in the opposite direction. I thus propose that you use the following moves (with some fixed probability distribution to choose which type of move to make) to perform a Markov chain on all possible sequences. In the following, a "run" is a maximum-length consecutive subsequence of balls of the same colour. This Markov chain relies on there being at least three colours.

  1. Pick two runs at random. If you can exchange them and still have a legal sequence, do so.

  2. Pick two adjacent runs. If you can exchange them and still have a legal sequence, do so.

  3. Pick two runs of the same colour. Redistribute the balls in them randomly among legal possibilities (so if the maximum number of balls in a single run was 3, and you had 5 balls total in the two chosen runs, the first one is equally likely to get 2 or 3 balls; if there were 3 balls total, the first is equally likely to get 1 or 2; if there were 4 balls total, 1, 2, and 3 are all equally likely).

  4. Pick some colour $C_i$ at random. Consider the sequence $S'$ of balls with all balls of colour $C_i$ removed. Now, pick at random two points in $S'$ where adjacent balls of different colours touch.

    a. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, and neither is maximum length, move a ball from one to the other, with each direction chosen with probability ½.

    b. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, but one is maximum length and the other is not, move a ball from the maximum length run to the shorter one with probability ½.

    c. If there is just one run of colour $C_i$ at one of these two points in $S$, with probability ½ move one ball from the run to the other point.

    d. If there is no run of colour $C_i$ at either of these points, or if there are runs of maximum length at both of these points, do nothing.

If my analysis is right, this is a reversible Markov chain that eventually converges to a uniform distribution of legal sequences of coloured balls, so if you run this chain for long enough, you will get very close to this uniform distribution.

How can you tell when this has converged? I would suggest watching the entropy of this sequence, and stop when it stops increasing. How do you compute the entropy? There are two main terms in the entropy calculation: the distribution of run lengths, and the sequence of colors each run has. For the distribution of run lengths, assume that there are $n_{i,k}$ runs of colour $i$ with length $k$. The contribution of these to the entropy is $$ \sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} }, $$ where $r$ is the maximum permissible length of a run. Now, let us consider the contribution of the colour sequence to the entropy. Suppose there are $m_{i,j}$ places where a run of colour $i$ is immediately followed by one of colour $j$ (so $m_{i,i}=0$). The contribution of this to the entropy is $$ \sum_i \ \log_2\ { \sum_j m_{i,j} \choose m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} }, $$ where $c$ is the number of colours.

(In the interest of accuracy, let me note that we are leaving out a number of contributions to the entropy, including the colour of the first ball, but these are lower order terms which should be safe to neglect.)

UPDATE:

There should be ways of speeding this up. I believe that for steps c and d, you can use analysis to perform both these steps over all runs of one color at once. For steps a and b, this is equivalent to the question of finding a random sequence of colored balls with the constraint that no two balls of the same color touch. There should be some good way of doing the mixing for this problem. Then you just have to alternate a/b steps with c/d steps, where each step mixes over those two moves completely. I think this should converge quite fast, although I don't have any rigorous analysis for this Markov chain.

$\endgroup$
0
$\begingroup$

As you said, it is not possible to ensure that every permutation is equally likely and ensure that the colors are evenly distributed, because one of the permutations has all the reds in a row.

A very elegant, but certainly not obvious, method to ensure the colors are evenly distributed is to leverage a low discrepancy sequence.

Suppose you have $N=400$ balls, numbered from $1$ to $N$, and a seed value, $s$.

Ensure that all balls of the same color are consecutively numbered. That is, in your case, let the first 100 balls be red, the next 40 be yellow, the next 50 green, etc.

Then, allocate the $k^{\textrm{th}}$ ball the value, $x_k$ such that: $$ x_k = (s+ k \phi) \; (\textrm{mod}\; 1),$$ where

  • $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$, the golden ratio
  • the $(\textrm{mod} \; 1)$ operator that takes the fractional part of argument
  • $s$ is any constant 'seed' value that you wish.

That is, each of the $N$ balls will be allocated a value of $x_k$ which will always between 0 and 1.

Now simply order the balls, in ascending order according to their $x_k$ value.

For example, using the seed value of $s=0$, the balls will be ordered as follows: $$ \{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 \} $$ (where "$B$"= Blue, and "$K$" = Black).

Finally, if you wish to take a different sample, simply select a different seed value, $s$.

Python code for this allocating the $x_k$ is as follows:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.