Python 中不同集合的成员之间的接近度最小排列集合成员的最佳算法

Question

我们有不同的套装。如何将不同的成员彼此相邻排列，以使同一组成员之间的距离最小？并且同一组中的两个成员尽可能不相邻？ 例如

s1 = [m1, m1, m1, m1, m1, m1, m1, m1, m1, m1]
s2 = [m2, m2, m2, m2, m2]
s3 = [m3, m3, m3]

结果一定是这样的：

r1 = [m1,m2, m1,m2, m1, m2, m1,m2, m1,m2, m1,m3, m1,m3, m1,m3, m1, m1]

注意：在这种情况下，可以将 s1 分成 n 组来避免这个问题。然后安排成员。并且n必须是最小数。

Answer 1

我没有实际证据证明这是最佳的。我确实知道它简单、快速且效果良好。

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)