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

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

对于初学者，您不需要检查所有子列表 -- 只需检查那些长度是完整列表长度的因子。

如果您主要关心编码的简单性而不是原始速度，只需让正则表达式引擎解决问题:

/^(.+?)\1+$/

这是 Abigail's awesome Perl regex to find prime numbers 的变体.