4

最近，我不得不重复一个字符串指定的次数。假设我必须有 5 个字符串“ bacon”副本，并且我的编辑器中有 1 行“ bacon”。所以我会从这个开始：

bacon

并以此结束：

bacon
bacon
bacon
bacon
bacon

让我们也定义三个“原子”操作：复制、粘贴和删除。“复制”允许您复制任意数量的行，“粘贴”粘贴最近复制的任何内容，“删除”删除一行。所以如果我有 3 行“ bacon”：

bacon
bacon
bacon

我想要 10 行“ bacon，”，我可以这样做：

copy 2  | lines of bacon: 3
paste 2 | lines of bacon: 5
copy 5  | lines of bacon: 5
paste 5 | lines of bacon: 10

但是，在i ≤ j的情况下，给定i行和j行所需的“原子”操作的最小数量是多少？是否有适用于这个问题的算法技术？还是我忽略了一些明显的东西？

4

3 回答 3

3

考虑一个序列删除然后粘贴。请注意，这会产生与粘贴后删除相同的状态。所以这些操作可以来回交换。

接下来考虑一个序列删除，然后是“副本 N”。请注意，这与“复制 N”后删除的状态相同，因此这些序列可以交换（但只能在一个方向上）。

因此，在任何操作序列中，我们都可以在不改变最终结果的情况下将任何删除操作与其后面的操作交换。因此，我们可以在不改变结果的情况下将所有删除操作移到最后。

由此可以得出，如果任何删除出现在最佳序列中，它们可以移动到序列的末尾：

XXXXXXXXDDDD

（其中 X 是 C 或 P）

但是没有后续粘贴的副本并不是最佳选择，因此序列实际上如下所示：

XXXXXXPDDDD

现在，观察到任何粘贴 + 删除 (PD) 序列都可以替换为复制 + 粘贴 (CP) 序列，其中副本只需少一行。这将两个操作替换为另外两个操作，因此它不会丢失任何内容。所以我们可以将我们的最优序列转化为：

XXXXXXCPDDD

我们可以再做三遍来消除所有的删除：

XXXXXXCCCCP

当然，副本序列是次优的，所以我们的答案必须如下所示：

XXXXXXCP

换句话说，删除永远不需要作为最佳序列的一部分。

从来不需要连续四次粘贴，因为它们总是可以用复制+粘贴+复制+粘贴代替。（不过，可能需要连续三个粘贴；例如从 4 到 13）

这就是我现在所能得到的。在这一点上，我可能只是做一个 Dijkstra 风格的广度优先搜索最短路径......

[更新]

正如马克彼得斯在评论中指出的那样，也永远不需要连续三个粘贴。证明：

Copy(N) 要求 N 小于行数。所以 Copy(N) + Paste + Paste + Paste 总是可以替换为 Copy(N) + Paste + Copy(2N) + Paste。

因此可以形成一个最佳序列，没有删除，连续没有两个副本，连续不超过两个粘贴。嗯，这是一个开始。

于 2012-05-01T04:17:10.973 回答
2

让我们规范化我们正在寻找的序列。这就像尼莫的回答一样。

  1. 有效序列由 D*(C[DP]*)* 匹配。重写 DC(n) → C(n) D 和 DP(n) → P(n) D。

  2. 有效序列由 (CP*)*D* 匹配。重写 C(n) D → D 和 P(n) D → C(n-1) P(n-1)。新副本是可以的，因为作为时间函数的缓冲区长度是单峰的。

  3. 有效序列由 (CP*)*|D* 匹配。

由于 i ≤ j，我们正在寻找的序列匹配 (CP*)*。

  1. 有效序列由 (CP*)* 匹配。重写 C(n) P(n) P(n) P(n) P(n) P(n) → C(n) P(n) C(2n) P(2n) P(2n) C(n) .

  2. 有效序列由 (CP{0,4})* 匹配。重写 C(n) C(n') → C(n')。

  3. 有效序列由 (CP{1,4})* 匹配。重写 C(n) P(n) P(n) P(n) P(n) → C(n) P(n) P(n) C(2n) P(2n)。我们不需要恢复副本，因为下一个命令（如果存在）是一个副本。

  4. 有效序列由 (CP{1,3})* 匹配。重写 C(n) P(n) P(n) P(n) → C(n) P(n) C(2n) P(2n)。我们不需要恢复副本。

我们正在寻找匹配的序列 (CP{1,2})*。缩写 2(n) = C(n) P(n) 和 3(n) = C(n) P(n) P(n)。如果它复制整个缓冲区，则调用复制整体，否则调用部分复制。如果它复制除一行之外的整个缓冲区，则调用几乎完整的副本。我将使用 w 和 p 以及 a 来注释命令。

让我们努力减少部分副本的数量。假设我们有 2p(n) … 2?(n')。我们可以重写为 2w(n+δ) ... 2p(n'-δ) 或 2w(n+n') ... ，减少部分副本的数量。我们可以对 3p(n) … 3?(n') 做同样的事情。假设最优，我们可以做 3p(n) … 2?(n')。我们不能被 3p(n+δ) … 2p(1) 困住，因为 3?(n+δ+1) … D 是等价的并且更短。我们可以做 2p(n) … 3?(n')，但 2 最终可能只是几乎完整的。

如果我们总是与伴侣一起处理最左边的部分副本，那么这种重写就会收敛。进一步改写后 2w(n) 3w(2n) → 3w(n) 2w(3n) 和 2w(n) 2w(2n) 2w(4n) 2w(8n) → 2w(n) 3w(2n) 3p(5n) ，有效序列由 2w{0,3} 3w* ( | 2p | 2a?3w* 3p ) 匹配。

log(n)-时间算法

显然，最优解的长度为 O(log(n))。我们可以计算每个解决方案中与上面的正则表达式匹配的 3w 个命令数量的下限和上限；这些界限相差一个统一的常数。尝试所有可能的短命令序列，其中有 O(log(n))。最多一份拷贝数量未指定；如果模式有效，很容易计算出它应该是什么。

于 2012-05-01T14:57:34.753 回答
2

复制+粘贴这两个操作最多可以使行数翻倍。操作与大小的比率为 2:2。如果您连续执行两次，您将获得 4 次操作的 4 倍。

三个操作，复制+粘贴+粘贴，最多可以使行数增加三倍。操作与行的比例为 3:3，或与之前相同。但是，如果您连续执行两次操作，您将获得 6 次操作的 9 倍，这是一个改进。

四种操作，复制+粘贴+粘贴+粘贴，可以使行数翻两番。再次，比例是相同的 4:4。如果您连续执行两次，则 8 次操作获得 16 倍。

五个操作，复制 + 4*粘贴，可以将行数乘以 5。但是结合两个和三个操作序列可以将行数乘以 6，以获得相同的操作数。如果您将这些推断出来，您会发现没有办法击败 2、3 和 4 操作序列的组合。

我的建议是使用 4 操作序列，直到结果在目标的 4 倍范围内，然后切换到 3 或 2 操作序列完成。

于 2012-05-01T04:08:22.793 回答