我正在寻找一种算法来缩减一个有序但不唯一的列表（播放列表）。
我尝试过集合理论，但还没有找到合适的内容。
例子：
[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.
想要获取所有现有的子列表并计算每个实例。 如果存在这样一个子列表，其中计数乘以子列表长度等于原始列表，则取最短的符合此条件的子列表。
这似乎有点粗暴，一定有更简单/更快的解决方案。
首先，您无需检查所有子列表--仅需要检查长度为完整列表长度的因子。
如果您主要关心的是编码简单性而不是原始速度，只需让正则表达式引擎解决问题：
/^(.+?)\1+$/
这是一个变体，基于 Abigail的神奇Perl正则表达式查找质数。
var str = "abcabc";
var regex = new Regex(@"/^(.+?)\1+$/");
var match = regex.Match(str); 这并没有产生任何结果。还尝试了
perl -e 'print /^(.+?)\1+$/' abcabc，但没有结果。 - kiteloop使用质数对每个集合元素进行编码。
例如：
a -> 2
b -> 3
c -> 5
现在，您需要再维护两个列表。
第一个列表是质数，第二个列表是它们的指数。
思路是：当您遇到一个元素时，记录它的质数和连续出现的次数。
对于[a, b, b, c]，您会得到这个：
[2, 3, 3, 5]
这可以被记录为：
[2, 3^2, 5]
或者，更准确地说：
[2^1, 3^2, 5^1]
而且你维护两个列表：
[2,3,5] // primes in succession - list [p]
[1,2,1] // exponents - list [e]
2^1*5^1 == 3^2*3^2; 由于它们不相同，因此无法缩小。[a, b, b, a, b, b]：[2^1, 3^2, 2^1, 3^2]
或者，
[2, 3, 2, 3] // primes
[1, 2, 1, 2] // exponents
现在，我们检查是否2^1 * 3^2 == 3^2 * 2^1（第一个质数，第一个指数乘以最后一个质数，最后一个指数，然后与第二个质数相比较下一个）
既然成立，那么它是可减的。
让我们试试[b，b，b，b，b]：
这可以编码为
[3^5]
或者，
[3] // primes
[5] // exponents
这是一个特殊情况：如果你有1个元素列表，那么你的原始列表是可缩小的。
让我们试试[b, b, b, b, a]：
这可以编码为
[3^4, 2^1]
或者，
[3, 2] // primes
[4, 1] // exponents
我们检查是否 3^4 == 2^1，由于不是这样，所以您的列表不可简化。
让我们尝试 [a, b, a, b, a, b]：
这可以编码为
[2^1, 3^1, 2^1, 3^1, 2^1, 3^1]
或者，
[2, 3, 2, 3, 2, 3]
[1, 1, 1, 1, 1, 1]
尝试上述过程是有效的，因为 2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1
因此，算法应该像这样：
将所有数字编码为质数。
遍历列表，按以下方式创建两个列表并填充它们
现在您拥有两个列表p和e，它们的长度均为n，请执行以下操作:
var start = p[0]^e[0] * p[n-1]^e[n-1]
var reducible = true;
for (int i = 0; i < n/2, ++i) :
if ( (p[i]^e[i] * p[n-i]^e[n-i]) != start ) :
reducible = false;
break;
n的长度来看，将原始列表缩减到其基本形式应该不太困难。这里有一些简单的代码，应该可以在接近线性时间内运行（最坏情况下O(n lg lg n)，我认为这依赖于一些高等数学）。
f(x) {
i = 1;
while (i <= size(x) / 2) {
if (size(x) % i != 0) { i++; continue;}
b = true;
for (j = 0; j + i < x.size(); j++) {
if (x[i] != x[j]) {
b = false;
break;
}
}
if (b) return i;
i = max(i + 1, j / i * i / 2); // skip some values of i if j is large enough
}
return -1;
}
基本上，以上代码执行了朴素算法，但跳过了一些周期性，因为早期的“近似匹配”已经被证明是不可能的。例如，如果您尝试一个周期为5并看到“aaaabaaaabaaaabaaaabab”，则可以安全地跳过6、7、...、10，因为我们看到了4个5的循环重复，然后失败了。
最终，您需要做线性数量的工作加上与sigma(n)成线性的工作量，其中n的约数之和sigma(n)受O(n lg lg n)的限制。
*请注意，证明此跳过的正确性相当微妙，我可能在细节上犯了错误--欢迎评论。
[a,b,b,c]和[b,b,b,b,a]的不可约性有什么规则？这个规则的直觉是什么？我问这个问题是因为它看起来像一个更一般的算法的特殊情况。根据你的第三条规则，[b,b]将（递归地）简化为[b]，[b,b,b,b] -> [b]也将如此简化。 - I GIVE CRAP ANSWERS