算法在不改变播放的情况下最小化播放列表

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 很棒的 Perl 正则表达式来查找素数。

Answer 2

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

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

Answer 3

用素数对每个集合元素进行编码。

例如：

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]

现在，您从末尾迭代这两个列表中间，检查第一个元素 [p]^[e] 是否与最后一个元素相同；如果是，那么第二个是倒数第二个，依此类推...如果所有这些都相同，则可以减少您的列表。

在此示例中，您检查是否 2^1*5^1 == 3^2*3^2；既然不是，就不能减少。

让我们尝试一下 [a, b, b, a, b, b]：

这被编码为

[2^1, 3^2, 2^1, 3^2]

or，

[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]

or，

[3]  // primes
[5]  // exponents

这是一种特殊情况：如果您有 1 个元素列表，那么您的原始列表是可简化的。

让我们尝试一下 [b, b, b, b, a]：

这可以编码为

[3^4, 2^1]

or，

[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]

or，

[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 的长度来看，应该不难看出如何将原始列表简化为其基本形式。

第二个注意：如果有人看到上面的错误，请纠正我。可能这一切都不起作用，因为已经很晚了，而且我的注意力也没有达到最佳状态。

Answer 4

这是一些简单的代码，应该以接近线性的时间运行（我认为最坏的情况是 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) 线性工作量，sigma(n) 是 n 的除数之和，其边界为 O(n lg lg n)。

*请注意，证明这种跳过的正确性非常微妙，我可能在细节上犯了错误——欢迎评论。