将字符串转换为另一个字符串的最小交换数

Question

问题陈述:

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

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 = sizeof(array)/sizeof(array[0]);
   int inversions = merge_sort(array, 0, array_size - 1);

   printf("Found %d inversions\n", inversions);
   return 0;
}

int merge_sort(int a[], int start, int end) {
   if ( end > start ) {
      int mid = start + (end - start) / 2;
      int x = merge_sort(a, start, mid);
      int y = merge_sort(a, mid + 1, end);
      int z = merge(a, start, mid, end);

      return x + y + z;
   }

   return 0;
}

int merge(int a[], int start, int mid, int end) {
   int l = start, r = mid + 1;
   int i = 0;
   int temp[end - start + 1];
   int splitInversionCount = 0;

   while ( l <= mid && r <= end ) {
       if ( a[l] < a[r] ) {
          temp[i++] = a[l++];
       }
       else {
         splitInversionCount += mid - l + 1;
         temp[i++] = a[r++];
       }
   }

   // copy whichever half of the array remains
   while ( l <= mid ) {
      temp[i++] = a[l++];
   }

   while ( r <= end ) {
      temp[i++] = a[r++];
   }

   // copy temp back into a
   int k;
   for(k = 0; k < i; k++) {
      a[k + start] = temp[k];
   }

   return splitInversionCount;
}

---

这样做的问题在于它给出了仅具有相邻元素的最小交换数量,4而不是3.

题:

有没有办法扩展此算法以捕获任意交换？或者我需要一种完全不同的方法？

Answer 1

我还没有完整的解决方案，但我认为陈述这一点以帮助其他人很有用。

我们假设字符串的大小为N。我们来计算k已经就位的字符数。最初k <= N

交换可以有：

1. 在正确的位置设置 2 个字符。增加k2
2. 在正确位置设置 1 个字符。增加k1
3. 不做任何有用的事情，k还是一样。

你总是可以进行第二种移动，并且可以在 O(n) 时间内找到它。只要从pos中取出一个字符，找到它需要的位置，然后交换即可。

你不应该一看到第一种类型就进行交换，因为你可能会破坏同时设置 2 个角色的其他动作。如果你这样做，你最终会在 3 步内设置 4 个字符，而你本可以在 2 步内完成。

进行第三种移动可以允许进行两次第一种移动，因此所有三种移动都是有用的。