1

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 permutations 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.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
Dominique
  • 21
  • 1
  • 4
    Possible duplicate of [I'd like to write an "ultimate shuffle" algorithm to sort my mp3 collection](https://softwareengineering.stackexchange.com/questions/194480/id-like-to-write-an-ultimate-shuffle-algorithm-to-sort-my-mp3-collection) – gnat Nov 30 '18 at 15:58
  • @gnat : I agree. Need to be deeply studied. – Dominique Nov 30 '18 at 16:07
  • 4
    "most random" hmm – Ewan Nov 30 '18 at 16:50
  • 1
    I think what Ewan is trying to say there is, it sounds like you have a requirement in mind that is not adequately conveyed by the single word, "random." Maybe you want to say something like, "no span of _n_ tea bags shall contain fewer than _m_ instances of any one flavor." (for some suitable choice of _n_ and _m_, of course.) – Solomon Slow Nov 30 '18 at 19:21
  • @SolomonSlow I think we can get by with a simple goal like: all valid sequences are equally likely. – candied_orange Nov 30 '18 at 19:52
  • Not unless you say what "valid" means. Is "ABABAB" a valid sequence? Your text above suggests that it is not. – Solomon Slow Nov 30 '18 at 20:13
  • This was earlier posted at https://scicomp.stackexchange.com/questions/30616/tea-bag-flavors-mixing-algorithm OP, who is new to these territories, ought to learn (see the Help Centre) that the Stack Exchange multiverse does not encourage posting the same question in more than one place. Note also that the question does have an answer in that other place. – High Performance Mark Nov 30 '18 at 20:33

0 Answers0