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

Question

当以下问题突然相关时，我正在浏览一个编程问题。

如何使用以下最少的交换将一个字符串转换为另一个字符串。字符串被保证可以相互转换(它们具有相同的字符集，这是给定的)，，但是字符可以重复。我看到了关于同一问题的网络搜索结果，但没有重复字符。
字符串中的任何两个字符都可以交换。

例如:可以在两次交换中将“aabbccdd”转换为“ddbbccaa”，在一次交换中将“abcc”转换为“accb”。

谢谢!

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}的置换，则 Action p(x)定义为组成p，然后是x。

组成为p的掉期次数最少，可以用p的循环分解表示。当j1，...，jk在{1，...，m}中成对区分时，周期(j1 ... jk)是一个置换，它将{1，...，m}中i的ji映射到ji + 1。 ，k-1}，将jk映射到j1，并将每个其他元素映射到自身。置换p是每个不同周期的组成(j p(j)p(p(j))... j')，其中j是任意的，p(j')= j。组成的顺序无关紧要，因为每个元素恰好出现在一个组成的循环中。 k个元素周期(j1 ... jk)可以写为k-1个周期的乘积(j1 jk)(j1 jk-1)...(j1 j2)。通常，每个置换可以写为m个交换的组成减去组成其周期分解的周期数。直接的归纳证明表明这是最佳的。

现在，我们深入了解Subhasis的答案。 提问者问题的实例与欧拉(对于每个顶点，度数等于度数)的二阶图G对应，顶点V和m的圆弧分别标记为1，...，m。对于{1，...，n}中的j，标记为j的弧从y(j)到x(j)。就G而言，问题在于确定将G的弧划分成有向循环的部分可以具有多少部分。 (由于G是欧拉矩阵，所以总是存在这样的分区。)这是因为如下所述，使得q(x)= y的排列q与这些分区一一对应。对于q的每个周期(j1 ... jk)，存在一个部分，其定向周期由标为j1，...，jk的弧组成。

与Subhasis的NP硬度降低有关的问题是，欧拉图上的弧不相交循环堆积是普通图上的弧不相交循环堆积的特殊情况，因此后者的NP硬度结果对复杂度没有直接影响。前者的地位。但是，在very recent work中(请参见下面的引文)，事实证明，即使是欧拉特例，也是NP-hard的。因此，通过上述对应关系，提问者的问题也同样存在。

正如Subhasis所暗示的，当字母的大小n固定(固定参数可处理)时，可以在多项式时间内解决此问题。由于在未标记弧时存在O(n!)个可区分的循环，因此我们可以在大小为O(mn)(可区分的子图的数量)的状态空间上使用动态编程。在实践中，这可能足以(假设)一个二进制字母，但是如果我尝试尝试在具有大字母的实例上精确地解决此问题，那么我可能会尝试分支定界，并通过使用线性编程来获得界限色谱柱的产生可以部分填充循环。

@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}
}