Algorithm to alternaly order elements in a list

So, I have N sets of objects of various sizes. I want to put them in order, in a way that's as much "alternative" as possible.

For example, if I have 5 A, and 6 b, that's easy: B A B A B A B A B A B

If I have 5 A, 6 B, and 2 C, it could be something like that: B A B A C B A B C A B A B

Any idea how I could compute that? It does not have to be that efficient, I'll have maybe 8 sets maximum, of maximum size 100. I do not have a specific criteria to evaluate how "alternative" the list is, but anything that looks good enough will do the trick. Thanks

• Is your aim to have no consecutive objects same? Nov 8 at 10:43
• Not necessarily, If I have 6A but 2B, I'll have no choice but to have consecutive objects. :) Nov 8 at 10:47

If you have no real criteria, you could do something like:

Input: couples (a1, n1), (a2, n2), …, (ak, nk)
Output: alternating array containing n1 occurrences of a1,
n2 occurrences of a2, …, nk occurrences of ak

for i = 1 to k:
mi ← ni
A ← empty array
while not all mi = 0:
let i ∈ {1, …, k} such that mi / (ni + 1) is maximal
append ai to A
mi ← mi - 1
return A


With your example, the order would be B A B A C B A B A C B A B.

• This looks great, thanks ! I'll try it quickly and tick your answer :) Nov 8 at 10:48
• Perfect, thank you :) Nov 8 at 10:55
• @AdrienNivaggioli Actually, you could consider mi / (ni + 1) instead of mi / ni to balance it a bit more without the need of sorting. That would also put elements with only one occurrence in the middle of the result instead of the beginning. Nov 8 at 11:03
• Absolutely, this is even better. Thank you so much! Nov 8 at 11:05