算法最小化播放列表而不改变播出

Question

我正在寻找一种算法来减少有序但不唯一的项目的列表(播放列表).搜索集合理论但尚未发现任何合适的东西

例子

[a, b, b, c] -> [a, b, b, c] Cannot be reduced. 
[a, b, b, a, b, b] -> [a, b, b]. 
[b, b, b, b, b] -> [b]. 
[b, b, b, b, a] -> [b, b, b, b, a] Cannot be reduced. 

考虑获取所有现有的子列表并计算每个实例.如果存在这样的子列表,其中子列表长度的计数时间等于原始列表,请选择与此条件匹配的最短子列表.

这似乎有点暴力,必须有一个更简单/更快的解决方案.

Answer 1

对于每个n <= N（其中N是列表的长度），ifn是 的一个因子N。如果是，则检查重复第一个n字符的子列表是否生成原始列表。如果是，那么您就找到了一个潜在的答案（答案是最短的）。在最坏的情况下，这应该会让你的效率低​​于O(N^2)蛮力，但仍然相同。

您可以通过注意以下事项进行一些修剪：例如，如果长度为 2 的子列表成功生成前 4 个字符但未生成完整列表，则长度为 4 的子列表将失败。您可以保留所有此类子列表长度的列表而不进行检查，这将减少一些计算。