algorithm - 元素混合算法

Question

不确定标题。

这是我需要的。

例如让这组元素 20*A, 10*B, 5*C, 5*D, 2*E, 1*F我需要混合它们，这样两个相同的元素就不会彼此相邻，而且我可以说我不希望 B 和 C 彼此相邻。元素必须均匀分布(如果有 2 个 E，一个应该在接近开始/上半场，第二个应该在接近尾声/在下半场。元素的数量当然可以改变。

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

Answer 1

我认为解决方案非常简单。

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

然后，对于按频率降序排列的每个 (item, frequency) 对，将 item 值分配给 x 从开始的交替槽中第一个 空 插槽。

以下是您的示例的工作原理:

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 仍然有一个空槽。请注意，我们本可以从一开始就确定这一点，因为我们在 A 之间至少需要 19 个槽位，但我们只有 18 个其他项。

更新

Leonidas 现在解释说元素应该“平均”分配(也就是说，如果我们有 k 个特定种类的元素，并且有 n 个槽位要填充，则 n/k 个槽位的每个“桶”必须包含一个元素那种。

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

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