Pythonでのスワップ操作後のハミング距離を最小化するプログラム

srcとtgtの2つの整数配列があり、どちらも同じ長さであるとします。また、allowedSwaps [i]にペア（ai、bi）が含まれている配列allowedSwapsもあります。これは、インデックスaiの要素を配列srcの要素インデックスbiと交換できることを示します。 （特定のインデックスのペアの要素を、任意の順序で何度でも交換できます）。同じ長さの2つの配列、srcとtgtのハミング距離は、要素が異なる位置の数です。配列srcに対して任意の量のスワップ操作を実行した後、srcとtgtの最小ハミング距離を見つける必要があります。

したがって、入力がsrc =[2,3,4,5]、tgt =[3,2,5,6]、allowedSwaps =[[0,1]、[2,3]]の場合、出力はsrcは次の方法で変換できるため、1になります。インデックス0と1を交換するため、ソース=[3,2,4,5]、インデックス2と3を交換するため、ソース=[3,2,5,4] 。ここで、srcとtgtのハミング距離は1の位置で異なるため、1です：インデックス3。

これを解決するには、次の手順に従います-

• グラフ：=srcと同じサイズのリストで、nを入力します
• 関数find（）を定義します。これにはxがかかります
• グラフ[x]はxと同じではありませんが、
  • グラフ[x]：=グラフ[グラフ[x]]
  • x：=グラフ[x]
• return x
• 関数union（）を定義します。これにはx、yが必要です
• x1：=find（x）、y1：=find（y）
• グラフ[x1]：=y1
• メインの方法から、次の手順を実行します
• allowedSwapsの各ペア（x、y）について、
  を実行します。
  • union（x、y）
• groups：=値がリストであるマップ、デフォルトではリストは空です
• 範囲0からsrc-1のサイズのiの場合、do
  • i1：=find（i）
  • グループの最後にiを挿入[i1]
• ans：=0
• グループのすべての値のリストにあるIDごとに、
  • counter：=カウント値を保持するための空のマップ
  • id内のidxごとに、
    を実行します。
    • counter [src [idx]]：=counter [src [idx]] + 1
    • counter [tgt [idx]]：=counter [tgt [idx]]-1
    • ans：=ans +（counterの値のリスト内のすべてのvarについて、valのすべての絶対値の合計）/ 2
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

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