0
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This looks great, thanks ! I'll try it quickly and tick your answer :) $\endgroup$ Nov 8 at 10:48
  • $\begingroup$ Perfect, thank you :) $\endgroup$ Nov 8 at 10:55
  • $\begingroup$ @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. $\endgroup$
    – Nathaniel
    Nov 8 at 11:03
  • $\begingroup$ Absolutely, this is even better. Thank you so much! $\endgroup$ Nov 8 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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