24

我正在查看一个编程问题，突然以下问题似乎相关。

如何使用如下的少量交换将一个字符串转换为另一个字符串。保证字符串是可相互转换的（它们具有相同的字符集，这是给定的），但字符可以重复。我在同一个问题上看到了网络结果，但没有重复字符。字符串中的任意两个字符都可以交换。

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

谢谢！

4

3 回答 3

8

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

形式上，问题是，给定一个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 1 , ..., j k在 {1, ..., m }中成对不同时，循环 ( j 1 ... j k ) 是将j i映射到j i + 1 for i in {1, ..., k - 1}，将j k映射到j 1，并将所有其他元素映射到自身。排列p是每个不同循环 ( j p ( j ) p ( p ( j )) ... j' ) 的组合，其中j是任意的，并且p ( j ') = j。组合的顺序无关紧要，因为每个元素恰好出现在一个组合循环中。一个k元素循环 ( j 1 ... j k ) 可以写成乘积 ( j 1 j k ) ( j 1 j k - 1 ) ... ( j 1 j 2 ) k - 1 个循环。一般来说，每个排列都可以写成m个交换减去组成其循环分解的循环数的组合。一个简单的归纳证明表明这是最优的。

现在我们进入了 Subhasis 答案的核心。提问者问题的实例与欧拉（对于每个顶点，入度等于出度）有向图G与顶点V和m弧标记为 1, ..., m一对一对应。对于{1, ..., n } 中的j ，标记为j的弧从y ( j ) 到x ( j )。关于G的问题是确定将G的弧划分为有向环的部分可以具有多少个部分。（由于G是欧拉，这样的分区总是存在的。）这是因为排列q使得q ( x ) = y与分区一一对应，如下所示。对于q的每个循环 ( j 1 ... j k ) ，都有一个部分，其有向循环由标记为j 1，...，j k的弧组成。

Subhasis 的 NP 硬度降低的问题在于，欧拉有向图上的弧不相交循环填充是一般有向图上弧不相交循环填充的特例，因此后者的 NP 硬度结果对复杂度状态没有直接影响前者。然而，在最近的工作中（参见下面的引文），已经表明，事实上，即使是欧拉特例也是 NP 难的。因此，通过上面的对应关系，提问者的问题也是如此。

正如 Subhasis 所暗示的，当字母表的大小n是固定的（固定参数易处理）时，这个问题可以在多项式时间内解决。由于弧未标记时有O ( n !) 个可区分循环，我们可以在大小为O ( m n )的状态空间上使用动态规划，即可区分子图的数量。在实践中，这对于（比方说）二进制字母表来说可能已经足够了，但是如果我要尝试在具有大字母表的实例上完全解决这个问题，那么我可能会尝试分支定界，通过使用线性规划获得界限使用色谱柱生成分步填充循环。

@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}
}
于 2014-05-15T20:10:08.197 回答
4

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

您现在可以构建一个“排列图” G ，它将具有n节点和从i到jif的边S[i] == S'[j]。在所有唯一字符的情况下，很容易看出所需的交换次数将是 (n - G 中的周期数)，可以在 O(n) 时间内找到。

但是，在有任意数量的重复字符的情况下，这减少了在有向图中找出最大循环数的问题，我认为这是 NP 难的，（例如查看：http：/ /www.math.ucsd.edu/~jverstra/dcig.pdf）。

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

  1. 在每一步，找到图中的最小长度循环（例如，在具有正权重的有向图中找到最短长度的循环）
  2. 删除它
  3. 重复直到所有顶点都没有被覆盖。

但是，可能存在利用您案例的属性的有效算法（我能想到的唯一一个是您的图表将是 K-partite，其中 K 是 中唯一字符的数量S）。祝你好运！

编辑：请参阅大卫的答案以获得对问题的更全面和正确的解释。

于 2013-08-18T01:49:01.567 回答
0

对从一个字符串到另一个字符串的等效字符串图的最短路径进行A* 搜索（参见http://en.wikipedia.org/wiki/A-star_search_algorithm以获得解释）。使用 Levenshtein 距离 / 2 作为成本启发式。

于 2013-08-17T20:39:15.310 回答