相关疑难解决方法(0)

我在接受采访时被问到这个问题,但我无法提出任何合适的解决方案.所以,我告诉他们找到所有周期然后选择长度最短的周期的天真方法.

我很想知道什么是这个问题的有效解决方案.

问题陈述:

找到将一个字符串转换为另一个字符串的最小交换次数,该字符串可能有也可能没有重复字符; 允许任意交换.

min_swaps('kamal', 'amalk') -> 3
#       1         2        3
# kamal -> lamak -> aamlk -> amalk

注意:SO上有很多这样的问题,但似乎没有一个适用于任意交换.

初步方法:

let s1 = 'kamal'
let s2 = 'amalk'

假设s1是"正确"排序,即它的元素0 -> N-1按递增顺序映射到序列.

0 1 2 3 4
k a m a l

现在创建一个数组P,它是从字母s2到s1中正确索引的映射:

1 2 3 4 0
a m a l k 

P = [1,2,3,4,0]

现在我们可以P使用修改后的mergesort 来计算数组反转的数量,这将为我们提供乱序的元素数量.

修改后的mergesort:

int main(int argc, char ** argv) {
   int array[] = { 1,2,3,4,0 };

   int array_size …

我在我正在开发的应用程序中遇到了以下问题:

我给了两个清单:

list1 = {Z,K,A,B,A,C}

list2 = {A,A,B,C,K,Z}

list2是保证是的排序版本list1.

我的目标是排序list1 仅通过交换单元内list1.因此,举例来说,我不能遍历list2,只是分配的每一个元素i中list1的每个元素j中list2.

使用list2作为一种资源,我需要排序list1的互换可能的绝对最低数量.

是否有专门用于此目的的一组算法？我没有听说过这样的事情.