在Python中最小化交换操作后的汉明距离的程序

假设我们有两个整数数组src和tgt，它们的长度相同。我们还有一个数组allowedSwaps，其中allowedSwaps [i]包含一对（ai，bi），表示我们可以交换数组src中索引ai处的元素与索引bi处的元素。（我们可以任意次序地交换特定索引对的元素）。因为我们知道相同长度的两个数组src和tgt的汉明距离是元素不同的位置数。我们必须在对数组src执行任意数量的交换操作后，找到src和tgt的最小汉明距离。

因此，如果输入如下：src = [2,3,4,5]，tgt = [3,2,5,6]，allowedSwaps = [[0,1]，[2,3]]，则输出将为1，因为src可以通过以下方式转换：交换索引0和1，因此source = [ 3,2,4,5]，交换索引2和3，所以源代码= [3,2,5,4]。这里，src和tgt的汉明距离为1，因为它们在1个位置不同：索引3。

要解决这个问题，我们将按以下步骤执行：

graph：大小与src相同的列表，用n填充
定义一个函数find()。这将获取x
当graph[x]与x不同时，执行以下操作
- graph[x]：=graph[graph[x]]
- x：= graph[x]
返回x
定义一个函数union()。这将获取x，y
x1：= find（x），y1：= find（y）
graph[x1]：=y1
从主方法中执行以下操作
对于允许的每一对（x，y），执行
- 联合（x，y）
groups：值为列表的映射，列表默认为空
对于范围在0到src大小-1的i，执行以下操作
- i1：= find（i）
- 在groups [i1]的末尾插入i
ans：= 0
对于groups所有值的列表中的每个ID，请执行以下操作
- counter：为空的映射以保存计数值
- 对于IDs中的每个idx，请执行以下操作
  - counter[src[idx]]：= counter[src[idx]] + 1
  - counter[tgt[idx]]：= counter[tgt[idx]]-1
  - ans：= ans +（对于counter.values()中的所有值的所有绝对值的总和，对于所有变量而言，它们在计数器的值列表中都是）/ 2
返回ans

例子

让我们看看以下实现，以更好的理解-。

from collections import defaultdict, Counter
def solve(src, tgt, allowedSwaps):
   graph = [ n for n in range(len(src)) ]

   def find(x):
      while graph[x] != x:
         graph[x] = graph[graph[x]]
         x= graph[x]
      return x

   def union(x, y):
      x1, y1 = find(x), find(y)
      graph[x1] = y1

   for x, y in allowedSwaps:
      union(x,y)

   groups = defaultdict(list)
   for i in range(len(src)):
      i1 = find(i)
      groups[i1].append(i)

   ans = 0
   for ids in groups.values():
      counter = Counter()
      for idx in ids:
         counter[src[idx]] += 1
         counter[tgt[idx]] -= 1
      ans += sum( abs(val) for val in counter.values())/2
   return ans

src = [2,3,4,5]
tgt = [3,2,5,6]
allowedSwaps = [[0,1],[2,3]]
print(solve(src, tgt, allowedSwaps))