我们给出了两个小写拉丁字母字母序列.它们的长度相同,并且具有相同数量的给定类型的字母(第一个具有与第二个相同数量的t,依此类推).我们需要找到将第一个序列转换为第二个序列所需的最小交换次数(通过"交换",我们的意思是改变两个相邻字母的顺序).我们可以安全地假设每两个序列可以相互转换.我们可以用蛮力做到这一点,但序列太长了.
输入:
序列的长度(至少2,最多999999),然后是两个序列.输出:
一个整数,表示序列变为相同所需的交换数.示例:
{5,aaaaa,aaaaa}应输出{0},
{4,abcd,acdb}应输出{2}.
我想到的第一件事是bubblesort.我们可以简单地对每个交换的序列进行计数.问题是:a)它是O(n ^ 2)最坏情况b)我不相信它会给我每个案例的最小数字......即使是优化的bubblesort似乎也没有做到这一点.我们可以实施鸡尾酒种类来解决海龟的问题 - 但它会给我最好的表现吗？或者也许有更简单/更快的东西？
这个问题也可以表述为:当允许的唯一操作是换位时,我们如何确定两个字符串之间的编辑距离？
小智 12
关于将置换转换为另一个所需的最小(不一定是相邻)交换次数,您应该使用的度量是Cayley距离,它基本上是置换的大小 - 周期数.
计算排列中的循环次数是一个非常微不足道的问题.一个简单的例子.假设置换521634.
如果你检查第一个位置,你有5个,在第5个你有3个,在第3个你有1个,关闭第一个循环.2处于第2位置,因此它自己进行循环,4和6进行最后一个循环(4位于第6位,6位位于第4位).如果要在身份排列中转换此排列(使用最小交换次数),则需要单独重新排序每个循环.交换的总数是置换的长度(6)减去周期数(3).
给定任何两个排列,它们之间的距离等于第一个的组成与第二个的倒数和身份之间的距离(如上所述计算).因此,您唯一需要做的就是组合第一个排列和第二个排列的倒数,并计算结果中的循环数.所有这些操作都是O(n),因此您可以在线性时间内获得最小数量的交换.
IVl*_*lad 10
这是一个简单而有效的解决方案:
我们Q[ s2[i] ] = the positions character s2[i] is on in s2.我们P[i] = on what position is the character corresponding to s1[i] in the second string.
建立Q和P:
for ( int i = 0; i < s1.size(); ++i )
Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of lists
temp[0 .. 25] = {0}
for ( int i = 0; i < s1.size(); ++i )
P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];
例:
1234
s1: abcd
s2: acdb
Q: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}
P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2
P[4] = 3
P有2反转(4 2和4 3),所以这就是答案.
这个解决方案是O(n log n)因为构建P并且Q可以完成O(n)并且合并排序可以计算倒数O(n log n).
小智 7
您正在寻找的可能与" Kendall tau距离 "相同,这是一致的负不一致对的(标准化的)差异.请参阅Wikipedia,声称它等同于冒泡排序距离.
在R中,函数不仅可用于计算tau,例如
cor( X, method="kendall", use="pairwise" ) ,
但也用于测试差异的重要性,例如
cor.test( x1, x2, method="kendall" ) ,
他们甚至能够恰当地考虑到关系.
“ Kendall tau distance ”算法是这种情况下的精确解决方案，其中必须找到相邻元素的交换次数。
例子。
eyssaasse （基本字符串）
seasysaes
基本字符串为每个元素提供索引：e =0、y =1、s =2、s =3、a =4 、 a =5、s =6、s =7、e =8；
有些元素是重复的，因此：
1) 创建一个字典，其中元素是键，值是索引列表：
idx = {' e '=>[0, 8], ' y '=>[1], ' s '=>[2, 3, 6, 7], ' a '=>[4, 5]}
2) 使用idx字典中的元素索引创建第二个字符串的索引映射：
seasysaes -> 204316587（循环 'seasysaes' 并从idx中每个键的列表中弹出下一个索引）
3）创建该图所有配对组合的列表，204316587：20 24 23 21 26 25 28 27 04 03 01 06 ... 65 68 67 58 57 87；
循环遍历这些对，计算第一个数字大于第二个数字的对。
该计数是所寻求的字符串之间相邻交换的数量。
Python脚本：
from itertools import combinations, cycle
word = 'eyssaasse' # base string
cmpr = 'seasysaes' # a string to find number of swaps from the base string
swaps = 0
# 1)
chars = {c: [] for c in word}
[chars[c].append(i) for i, c in enumerate(word)]
for k in chars.keys():
chars[k] = cycle(chars[k])
# 2)
idxs = [next(chars[c]) for c in cmpr]
# 3)
for cmb in combinations(idxs, 2):
if cmb[0] > cmb[1]:
swaps += 1
print(swaps)
“eyssaasse”和“seasysaes”之间的交换次数为 7。
“reviver”和“vrerevi”之间的交换次数为 8。