找到将一个字符串转换为另一个字符串的最小交换次数，其中字符串可能包含重复字符。

Question

我正在查看一个编程问题时，突然冒出了以下问题。

如何使用尽可能少的交换将一个字符串转换为另一个字符串。这些字符串保证可以相互转换（它们具有相同的字符集，这是给定的），但字符可以重复。我在网上看到了关于同样问题的结果，但没有字符被重复。

例如："aabbccdd" 可以在两次交换中转换为 "ddbbccaa"，而 "abcc" 可以在一次交换中转换为 "accb"。

谢谢！

- piedpiper

---

无论如何，计算两个字符串之间的Levenshtein距离将给出交换的数量（因为在您的特定情况下，Levenshtein算法检测到的所有操作都是交换）。 - Geeky Guy

@Renan：那abccab变成abcabc怎么样？ - P0W

@P0W 两个字符不匹配，交换一个即可解决。Levenshtein距离也是两个...哦，我明白了我的错误。在这里计算的任何Levenshtein距离实际上都会是正确答案的两倍。 - Geeky Guy

@Renan：abccab和abcabc的最后3个字符不匹配。 - P0W

有任何更新或对任何答案的反馈吗？ - bsd

Answer 1

这是Subhasis's answer的扩展和修正版本。

形式上，问题是：给定一个有n个字母的字母表V和两个m个字母的单词x和y，使得存在一个置换p，使得p(x)=y，确定最少需要多少次交换（保持所有元素不变的置换）其组合q满足q(x)=y。假设n个字母的单词是从集合{1, ..., m}到V的映射，并且p和q是在{1, ..., m}上的置换，则操作p(x)定义为先进行p再进行x的组合。

最少的交换次数，其组合为p，可以用p的循环分解来表示。当j₁，...，j_k在{1，...，m}中成对不同，则循环（j₁ ... j_k）是一个置换，将j_i映射到j_i+1，其中i在{1，...，k-1}中，将j_k映射到j₁，并将其他每个元素映射到自身。置换p是每个不同循环（j p（j）p（p（j））... j'）的组合，其中j是任意的，且p（j'）= j。由于每个元素仅出现在一个组合的循环中，因此组合的顺序无关紧要。一个k元循环（j₁ ... j_k）可以写成k-1个循环的乘积（j₁ j_k）（j₁ j_k-1）...（j₁ j₂）。通常情况下，每个置换都可以写成m个交换的组合减去其循环分解所包含的循环数。一种直接的归纳证明表明这是最优的。

现在我们来到Subhasis的答案核心。询问者问题的实例与Eulerian（每个顶点的入度等于出度）有向图G具有顶点V和m个标记为1，...，m的弧一一对应。对于{1，...，n}中的j，标记为j的弧从y（j）到x（j）。根据G的问题是确定将G的弧划分为定向循环的部分数。 （由于G是Eulerian，因此始终存在这样的分区。）这是因为置换q（x）= y的排列与分区一一对应，如下所示。对于q的每个循环（j1 ... jk），都有一个由标记为j1，...，jk的弧组成的定向循环的部分。

Subhasis的NP难度规约问题在于欧拉有向图上的弧不相交环路包装是一般有向图上弧不相交环路包装的特殊情况，因此对于后者的NP难度结果对前者的复杂性状态没有直接的影响。但是，在最近的工作（见下面的引用）中，已经证明了即使是欧拉特殊情况也是NP难的。因此，通过上述对应关系，提问者的问题也是NP难的。

正如Subhasis所暗示的那样，当字母表的大小n固定时（固定参数可解），可以在多项式时间内解决这个问题。由于当弧未标记时有O（n！）可区分的循环，因此我们可以在状态空间为O（mⁿ）即可区分子图的数量上使用动态规划。实际上，对于（假设）二进制字母表，这可能已经足够了，但如果我尝试在具有大型字母表的实例上精确解决此问题，则可能会尝试使用分支界限法，通过使用线性规划和列生成来分数地打包循环以获得边界。

@article{DBLP:journals/corr/GutinJSW14,
  author    = {Gregory Gutin and
               Mark Jones and
               Bin Sheng and
               Magnus Wahlstr{\"o}m},
  title     = {Parameterized Directed \$k\$-Chinese Postman Problem and \$k\$
               Arc-Disjoint Cycles Problem on Euler Digraphs},
  journal   = {CoRR},
  volume    = {abs/1402.2137},
  year      = {2014},
  ee        = {http://arxiv.org/abs/1402.2137},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

- David Eisenstat

---

谢谢David。在我发表评论之前，我没有看过你的答案。我会阅读这篇论文。 - Subhasis Das

Answer 2

您可以构造“差异”字符串S和S'，即包含两个字符串不同位置的字符的字符串，例如，对于acbacb和abcabc，它将是cbcb和bcbc。假设这包含了n个字符。

现在，您可以构造一个“置换图”G，该图将具有n个节点，并从i到j拥有一条边，如果S[i] == S'[j]。对于所有唯一字符的情况，很容易看出所需交换的数量为（n- G中循环数），可以在O(n)时间内找到。

但是，在存在任何数量的重复字符的情况下，这就降到了找到有向图中最大循环次数的问题，我认为这是NP-hard的（例如，请查看：http://www.math.ucsd.edu/~jverstra/dcig.pdf ）。

在那篇论文中，指出了一些贪心算法，其中一个特别简单：

1. 在每个步骤中，找到图中最小长度的周期（例如，寻找带正权重的有向图中最短长度的周期） 2. 删除它 3. 重复，直到所有的节点都被覆盖。

然而，可能存在利用您情况属性的有效算法（我能想到的唯一一个是，您的图形将是K部分的，其中K是S中唯一字符的数量）。祝你好运！

编辑： 有关该问题的更完整和正确的解释，请参阅David的答案。

- Subhasis Das

---

在每个顶点的入度等于出度的图族中，循环包装的硬度结果是否成立？ - David Eisenstat

我对“在所有唯一字符的情况下，很容易看出所需交换次数为（n-G中的循环数）”感到困惑。如果所有字符都是唯一的，则G中的每个顶点恰好与1条边相交，因此将没有任何循环。另外，O(n*log(n))时间是否指测试是否存在任何重复项？这可以在线性时间内完成。 - j_random_hacker

对于混淆感到抱歉。考虑S =“bcdef”和S' =“cbfde”。在这种情况下，G在（1->2）（S中的第一个字符= S'中的第二个字符），（2->1），（3->4），（4->5），（5->3）之间有一条边。因此有两个循环，（1->2->1）和（3->4->5->3）。请注意，每个循环可以在（＃元素_在_循环中-1）步内修复。因此，您可以在\ sum_cycles {#elements-1}中修复整个字符串，其中n-＃cycles。 - Subhasis Das

@DavidEisenstat，我不确定那个具体情况。如果你了解到任何信息，请告诉我。 - Subhasis Das

@j_random_hacker 你是正确的。对于循环情况而言，该算法基本上等价于查找强连通分量，时间复杂度为O(n)。我已经修改了我的回答。 - Subhasis Das

@SubhasisDas：最后我的困惑是我自己的错--我不知怎么地认为G是无向的。而且我很高兴我的（错误的）时间限制猜测导致了一个无关的改进 :) - j_random_hacker

Answer 3

进行 A* 搜索（请参见 http://en.wikipedia.org/wiki/A-star_search_algorithm 进行说明），以找到从一个字符串到另一个字符串的等效字符串图中的最短路径。使用莱文斯坦距离 / 2 作为成本启发式。

- btilly