均匀混合两个元素列表（负载平衡）

Question

假设我有两个只有 1 个字符的字符串：

'aaaaaaa'
'bbb'

我想找到一种算法来生成以下组合字符串：

'aabaabaaba'

将两者合并，以便每个列表中连续字符的数量最少（在本例中，# 为 2）。每个字符串的长度是任意的，我希望它是对称的。将其扩展到不仅仅是 2 个字符串的奖励积分。

我在 python 中这样做，但语言无关紧要。这是我正在处理的负载平衡问题。

Answer 1

您可以交替使用这些元素，并在必要时使用较长字符串中的一个字母。您可以确定是否可以使用整数运算来增加一个字母：分数告诉您每个字母对之间有多少个字母。你累积这个分数并使用较长数组中的字母，只要累积的分数大于 ½:

def intertwine(a, b):
    """ Return a combination of string with fewest number of
        consecutive elements from one string
    """

    if len(b) > len(a):
        return intertwine(b, a)

    if not b:
        return a

    a = list(a)
    b = list(b)

    num = len(a) - len(b)
    denom = len(b)
    acc = 0

    res = []

    while a or b:
        acc += num

        while acc >= denom / 2:
            if a: res += a.pop(0)
            acc -= num

        if a: res += a.pop(0)
        if b: res += b.pop(0)

    return "".join(res)



print intertwine("aaabaaa", "bbb")      # "aababbaaba"
print intertwine("aaaaaaa", "b")        # "aaabaaaa"
print intertwine("aaaaaa", "b")         # "aaabaaa"
print intertwine("aa", "bbbbbb")        # "bbabbabb"
print intertwine("", "bbbbbb")          # "bbbbbb"
print intertwine("", "")                # ""

Answer 2

import itertools

def intermix(*containers):
    mix = []
    for c in sorted(containers, key=lambda c: len(c)):
        if len(c) >= len(mix):
            bigger, smaller = c, mix
        else:
            bigger, smaller = mix, c
        ratio, remainder = divmod(len(bigger), len(smaller) + 1)
        chunk_sizes = (ratio + (1 if i < remainder else 0) for i in range(len(smaller) + 1))
        chunk_offsets = itertools.accumulate(chunk_sizes)
        off_start = 0
        new_mix = []
        for i, off in enumerate(chunk_offsets):
            new_mix.extend(bigger[off_start:off])
            if i == len(smaller):
                break
            new_mix.append(smaller[i])
            off_start = off
        mix = new_mix
    return mix

均匀混合两个元素列表（负载平衡）

Evenly intermix two lists of elements (load balance)

python

arrays

algorithm

load-balancing

sequence