I bought three boxes of tea bags with different flavors (A, B, C).

I wish to mix them in such a way that - there is never two consecutive bags of the same flavor (ABCCAB is avoided) ; - the mixing is the "most" random, i.e. avoid patterns such as ABCABCABC... or ABABAB...BCBCBC...CACACA.

Is there a known algorithm for this mix?

Presently I randomly shuffle many "ABC" and concatenate the results, swapping the first letters if the latest letter of the previous shuffle is the same than the beginning of the new shuffle (...ABCCAB => ...ABCACB).

I guess I could improve this algorithm by pre-computing the permutations of ABC, and draw one permutation among the ones who do not begin with the same letter than the previous permutation.

I tried to "google" this problem but as a French native speaker, I probably miss the appropriate key-words.

  • 1
    $\begingroup$ I'm not sure that this is the right site for your question, it doesn't seem to have much to do with Computational Science. Perhaps it would be better asked at stackoverflow.com. $\endgroup$ – High Performance Mark Nov 30 '18 at 10:32
  • $\begingroup$ If this is homework, can you mark it as such? What is the underlying problem you are trying to solve? $\endgroup$ – Kirill Nov 30 '18 at 12:33
  • $\begingroup$ As a teacher, I give homeworks, not do them :). The problem is exactly what I exposed : I have three boxes of tea bags and want to mix them to avoid having only one flavor at the end, if I draw them. Moreover, the algorithm, if it exit, could be used for producing a random list of "calls to the chalkboard" for my students, avoiding to call the same student two times consecutively. I guess there are other uses. $\endgroup$ – Dominique Nov 30 '18 at 14:11

The first idea that would come to my mind naturally is: after each bag, choose with 50% probability one of the remaining two. Does this avoid "special" patterns such as ABABAB? No, they just have a low chance of appearing. And that's how it should be, in a true random number generator. Avoiding special patterns give the impression of randomness, but true random numbers may have them (exactly as you have already noticed with equal consecutive numbers).

| cite | improve this answer | |

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