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

Question

我正在查看一个编程问题,当下面的问题突然变得相关时.

如何使用如下几个交换将字符串转换为另一个字符串.字符串保证是可互换的(它们具有相同的字符集,这是给出的),但字符可以重复.我在同一个问题上看到了网页结果,但没有重复字符.字符串中的任何两个字符都可以交换.

例如:"aabbccdd"可以在两次交换中转换为"ddbbccaa",并且"abcc"可以在一次交换中转换为"accb".

谢谢!

Answer 1

这是Subhasis的答案的扩展和更正版本.

形式上,问题是,给定一个n字母字母V和两个m字母x和y,其中存在一个排列p,使得p(x)= y,确定最小的交换数量(修正的排列)除了两个元素之外的所有元素,其组成q满足q(x)= y.假设n -letter字是从集合{1,...,m }到V以及p和q的映射对于{1,...,m }的排列,动作p(x)被定义为组合p,后跟x.

数最少的互换,其组成是p可在的周期分解来表示p.当Ĵ ₁,...,Ĵ _ķ是成对不同在{1,...,米 },周期(Ĵ ₁ ... Ĵ _ķ)是映射的置换Ĵ _我到Ĵ _{我 + 1}用于我在{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的答案的核心.提问者的问题的实例对应一个对一具有欧拉(对于每个顶点,在度等于出度)有向图G ^与顶点V和米标记为1,...,弧米.对于Ĵ在{1,...,Ñ },电弧标记Ĵ从进入ý(Ĵ)到X(Ĵ).G方面的问题是确定G的弧线到定向循环的分区有多少部分.(由于G是欧拉,所以这样的分区总是存在.)这是因为排列q使得q(x)= y与分区一一对应,如下所述.对于q的每个周期(j ₁ ... j _k),存在其定向周期由标记为j ₁,...,j _k的弧组成的部分.

Subhasis的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}
}