我正在查看一个编程问题时,突然冒出了以下问题。
如何使用尽可能少的交换将一个字符串转换为另一个字符串。这些字符串保证可以相互转换(它们具有相同的字符集,这是给定的),但字符可以重复。我在网上看到了关于同样问题的结果,但没有字符被重复。
例如:"aabbccdd" 可以在两次交换中转换为 "ddbbccaa",而 "abcc" 可以在一次交换中转换为 "accb"。
谢谢!
这是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的循环分解来表示。当j1,...,jk在{1,...,m}中成对不同,则循环(j1 ... jk)是一个置换,将ji映射到ji+1,其中i在{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的NP难度规约问题在于欧拉有向图上的弧不相交环路包装是一般有向图上弧不相交环路包装的特殊情况,因此对于后者的NP难度结果对前者的复杂性状态没有直接的影响。但是,在最近的工作(见下面的引用)中,已经证明了即使是欧拉特殊情况也是NP难的。因此,通过上述对应关系,提问者的问题也是NP难的。
正如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}
}
S
和S'
,即包含两个字符串不同位置的字符的字符串,例如,对于acbacb
和abcabc
,它将是cbcb
和bcbc
。假设这包含了n个字符。n
个节点,并从i
到j
拥有一条边,如果S[i] == S'[j]
。对于所有唯一字符的情况,很容易看出所需交换的数量为(n- G中循环数),可以在O(n)时间内找到。S
中唯一字符的数量)。祝你好运!进行 A* 搜索(请参见 http://en.wikipedia.org/wiki/A-star_search_algorithm 进行说明),以找到从一个字符串到另一个字符串的等效字符串图中的最短路径。使用莱文斯坦距离 / 2 作为成本启发式。
abccab
变成abcabc
怎么样? - P0Wabccab
和abcabc
的最后3个字符不匹配。 - P0W