We have different sets. How to arrange different members next to each other in such a way that there is the least proximity between the members of the same set? And as much as possible none of the two members of the same set are next to each other? For example
s1 = [m1, m1, m1, m1, m1, m1, m1, m1, m1, m1]
s2 = [m2, m2, m2, m2, m2]
s3 = [m3, m3, m3]
And the result must be something like this:
r1 = [m1,m2, m1,m2, m1, m2, m1,m2, m1,m2, m1,m3, m1,m3, m1,m3, m1, m1]
Notice: In this case, it is possible to split s1 into n sets to void this problem. And then arrange members. And n must be the minimum number.
I don't have an actual proof that this is optimal. I only suspect that it is. However I do know that it is simple, fast, and produces good results.
def distribute (count_by_kind):
total_count = 0
kinds = []
current_weight = []
for kind, count in count_by_kind.items():
total_count += count
kinds.append(kind)
current_weight.append(0)
max_i = -1
max_weight = -1
for _ in range(total_count):
for i, kind in enumerate(kinds):
current_weight[i] += count_by_kind[kind] / total_count
if max_weight < current_weight[i]:
max_weight = current_weight[i]
max_i = i
yield kinds[max_i]
# Bookkeeping for the nexgt pass.
current_weight[max_i] -= 1
max_i = -1
max_weight = -1
# An example of how to use it.
for x in distribute({"a": 5, "b":6, "c": 15}):
print(x)
Incidentally this is cyclic. If you were to multiply all of the counts by n, you'll just get the same pattern repeated n times. If you wish to make the results unpredictable, you could initialize with a random number instead of 0. However then the most common element won't come first, which means that you might get an extra repeat.