0

不确定标题。

这是我需要的。

例如，让这组元素 20*A、10*B、5*C、5*D、2*E、1*F 我需要混合它们，所以没有两个相同的元素彼此相邻，我也可以例如说我不希望 B 和 C 彼此相邻。元素必须均匀分布（如果有 2 个 E，则一个应该接近开始/第一半，第二个接近结束/后半。元素的数量当然可以改变。

我还没有做过这样的事情。是否有这种算法的一些知识库，我在哪里可以找到一些提示和方法来解决这种问题，还是我必须自己做所有的数学？

4

3 回答 3

1

我认为解决方案很简单。

x从一个初始化为值的数组开始，empty这样您需要放置的每个项目都有一个空间。

然后，对于(item, frequency)按频率降序排列的每一对，从第一个时隙开始在交替时隙中分配item值。xempty

以下是它对您的示例的工作方式：

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABABABABABABABABABABA_A_A_A_A_A_A_A_A_A
 5*C    ABABABABABABABABABABACACACACACA_A_A_A_A
 2*E    ABABABABABABABABABABACACACACACAEAEA_A_A
 1*F    ABABABABABABABABABABACACACACACAEAEAFA_A

此时我们失败了，因为x仍然有一个空槽。请注意，我们可以从一开始就确定这一点，因为我们需要在 s 之间至少有 19 个插槽A，但我们只有 18 个其他项目。

更新

列奥尼达斯现在解释说，物品应该“均匀”分布（也就是说，如果我们有 k 个特定种类的物品，并且有 n 个插槽要填充，那么 n/k 个插槽的每个“桶”必须包含一个该类型的物品。

我们可以通过分散分配而不是简单地使用交替插槽来适应这种限制。在这种情况下（让我们假设 2 Fs，这样我们就可以解决这个问题），我们会有

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA
 5*C    ABACABA_ABACABA_ABACABA_ABACABA_ABACABA
 2*E    ABACABAEABACABA_ABACABAEABACABA_ABACABA
 2*F    ABACABAEABACABAFABACABAEABACABAFABACABA
于 2013-02-20T22:30:09.857 回答
0

你可以递归地解决这个问题：

def generate(lastChar, remDict):
    res = []
    for i in remDict:
        if i!=lastChar):
            newRemDict = remDict
            newRemDict[i]-=1
            subres = generate(i,newRemDict)
            res += [i+j for j in subres]
    return res

请注意，我忽略了角落条件和许多需要完成的检查。但只显示了核心递归。如果剩余字母中有超过一半+1是同一个字母，您也可以退出追求一个分支。

于 2013-02-20T22:42:29.373 回答
0

我遇到了类似的问题，在评估了各种指标后，我想出了抓取第一个通过源数组的比例小于通过结果数组的比例的项目的想法。在某些情况下，所有这些值都可能显示为 1，例如，在合并一组偶数数组的中途 - 一切都完成了一半 - 所以在这种情况下我从第一个数组中抓取一些东西。

该解决方案确实使用了源数组顺序，这是我想要的。如果调用例程想要合并数组 A、B 和 C，其中 A 有 3 个元素，而 B 和 C 有 2 个元素，我们应该得到 A,B,C,A,B,C,A，而不是 A,C,B ,A,C,B,A 或其他可能性。我发现选择我的第一个“过期”的源数组（通过比例低于我们的整体进度），我得到了一个很好的所有数组间距。

Python 中的源代码：@classmethod def intersperse_arrays(cls, arrays: list): # 这里的一般想法是在我们下降时在所有数组之间产生尽可能平衡的结果。

    # Make sure we don't have any component arrays of length 0 to worry about.
    arrays = [array for array in arrays if len(array) > 0]

    # Handle basic cases:
    if len(arrays) == 0:
        return []
    if len(arrays) == 1:
        return arrays[0]

    ret = []
    num_used = []
    total_count = 0
    for j in range(0, len(arrays)):
        num_used.append(0)
        total_count += len(arrays[j])

    while len(ret) < total_count:
        first_overdue_array = None
        first_remaining_array = None
        overall_prop = len(ret) / total_count

        for j in range(0, len(arrays)):
            # Continue if this array is already done.
            if len(arrays[j]) <= num_used[j]:
                continue
            current_prop = num_used[j] / len(arrays[j])
            if current_prop < overall_prop:
                first_overdue_array = j
                break
            elif first_remaining_array is None:
                first_remaining_array = j

        if first_overdue_array is not None:
            next_array = first_overdue_array
        else:
            # Think this only happens in an exact tie.  (Halfway through all arrays, for example.)
            next_array = first_remaining_array

        if next_array is None:
            log.error('Internal error in intersperse_arrays')
            break   # Shouldn't happen - hasn't been seen.

        ret.append(arrays[next_array][num_used[next_array]])
        num_used[next_array] += 1

    return ret

在给出的示例中使用时，我得到：

ABCADABAEABACABDAFABACABADABACDABAEABACABAD

（看起来很合理。）

于 2016-09-14T16:37:17.223 回答