我们给出了两个小写拉丁字母字母序列.它们的长度相同,并且具有相同数量的给定类型的字母(第一个具有与第二个相同数量的t,依此类推).我们需要找到将第一个序列转换为第二个序列所需的最小交换次数(通过"交换",我们的意思是改变两个相邻字母的顺序).我们可以安全地假设每两个序列可以相互转换.我们可以用蛮力做到这一点,但序列太长了.
输入:
序列的长度(至少2,最多999999),然后是两个序列.输出:
一个整数,表示序列变为相同所需的交换数.示例:
{5,aaaaa,aaaaa}应输出{0},
{4,abcd,acdb}应输出{2}.
我想到的第一件事是bubblesort.我们可以简单地对每个交换的序列进行计数.问题是:a)它是O(n ^ 2)最坏情况b)我不相信它会给我每个案例的最小数字......即使是优化的bubblesort似乎也没有做到这一点.我们可以实施鸡尾酒种类来解决海龟的问题 - 但它会给我最好的表现吗？或者也许有更简单/更快的东西？
这个问题也可以表述为:当允许的唯一操作是换位时,我们如何确定两个字符串之间的编辑距离？
例如,输入是
Array 1 = [2, 3, 4, 5]
Array 2 = [3, 2, 5, 4]
需要的最小交换次数是2.
交换不需要与相邻的单元相交,任何两个元素都可以交换.
设A为列表,S为相同元素的排序列表.假设所有元素都不同.如何找到move X before Y (or end)将A变为S 的最小"移动"()？
例子:
A = [8,1,2,3]
S = [1,2,3,8]
A => S requires one move:
move 8 before end
A = [9,1,2,3,0]
S = [0,1,2,3,9]
A => S requires two moves:
move 9 before 0
move 0 before 1
我更喜欢javascript或python,但任何语言都可以.