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.