1

可能重复:
分离相同类型项目的算法

我朋友的项目中有一个有趣的问题。他从事电视广告投放工作。广告属于不同类型:移动、食品、银行等。他需要重新排列广告列表,以便将相似类型的广告放置在彼此之间的最大距离处。一个广告块中大约有 100 个广告,因此暴力解决方案是不可行的。是否有可能提出一个相当快的解决方案(<30 秒)?最快的方法是什么?

假设每个广告的长度相同。

示例:
[M, M, F, B, F, B]。在这种特殊情况下,输出可能是:[M, F, B, M, F, B]

4

1 回答 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 回答