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

• Z时代
• 2024-01-10
• 分类：综合

假设我们有两个整数数组，src 和 tgt，它们的长度相同。我们还有一个数组 allowedSwaps，其中 allowedSwaps[i] 包含一对 (ai, bi) 表示我们可以将索引 ai 处的元素与数组 src 的元素索引 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，所以源 = [3,2,4,5]，交换索引 2 和 3，所以源 = [3,2,5,4] . 这里 src 和 tgt 的汉明距离为 1，因为它们在 1 个位置不同：索引 3。

示例

让我们看看以下实现以获得更好的理解 -

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))

输入

[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]

1

以上是 在 Python 中交换操作后最小化汉明距离的程序 的全部内容， 来源链接： utcz.com/z/360742.html