可能重复：
分离相同类型项目的算法
我朋友的项目中有一个有趣的问题。他从事电视广告投放工作。广告属于不同类型：移动、食品、银行等。他需要重新排列广告列表，以便将相似类型的广告放置在彼此之间的最大距离处。一个广告块中大约有 100 个广告，因此暴力解决方案是不可行的。是否有可能提出一个相当快的解决方案（<30 秒）？最快的方法是什么？
假设每个广告的长度相同。
示例：
[M, M, F, B, F, B]。在这种特殊情况下，输出可能是：[M, F, B, M, F, B]
问问题
206 次
1 回答
1
假设您想最大化最小距离。首先，计算您拥有的每种类型项目的数量（所有这些项目的总和应该是n列表中的项目数 , ）。根据频率对唯一种类的项目列表进行排序。然后，准备一个带有n单元格的输出磁带。从最频繁的元素开始，定期将元素均匀地放置在输出磁带中。继续按项目频率的降序排列，只考虑磁带上的空单元格。这是O(n + m log m)，其中n是项目的总数，m是唯一项目的数量（即项目的种类）。请注意，在这种情况下，您可能无法对项目种类使用线性排序算法，因此您可能会丢失log m因素，虽然在实践中（对于 100 个项目，并且可能是更少种类的项目）我不知道这是否值得。
在您的示例中：[M，M，F，B，F，B]。我们有 (M, 2), (F, 2), (B, 2)。第一遍后我们得到 [M, _, _, M, _, _]，第二遍后得到 [M, F, _, M, F, _] 和 [M, F, B, M, F, B]第三次之后。
请注意，这是一种启发式方法，我怀疑它可能是最优的，但我并没有试图证明这是最优的，甚至对我自己也没有。但是，如果您有n元素并且最频繁的元素出现x次数，那么最小距离可能是floor(n/x)（编辑：这实际上不是真的，请参阅我的评论）......这就是这个启发式的目标。我想有一个问题，如果数字甚至不是除数，如何“均匀地”间隔项目......但即使对于我尝试发生这种情况的示例，几乎任何选择都是可以的，我们正在优化的标准. 一个稍微难一点的例子：
[A, A, A, A, A, B, B, B, C, C, D] 给我们 (A, 5), (B, 3), (C, 2), (D, 1)；第一遍后我们得到[A,_,A,_,A,_,A,_,A,_,_]，[A,B,A,_,A,B,A,_,A,B , _] 在第二遍之后， [A, B, A, C, A, B, A, C, A, B, _] 在第三遍之后得到 [A, B, A, C, A ，B，A，C，A，B，D]。对于政府工作来说已经足够了。
事实上，我想不出比这更好的简单方法来最小化平均距离。这应该很快......它是否足以满足您朋友的需求？
于 2012-12-20T17:22:04.733 回答