How to shuffle colour balls? 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.
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.


Pick two runs at random. If you can exchange them and still have a legal sequence, do so.
Pick two adjacent runs. If you can exchange them and still have a legal sequence, do so.
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).
Pick some colour $C_i$ at random. Consider the sequence $S&#39;$ of balls with all balls of colour $C_i$ removed. Now, pick at random two points in $S&#39;$ 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 &frac12;. 

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 &frac12;.

c. If there is just one run of colour $C_i$ at one of these two points in $S$, with probability &frac12; 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.