Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình giảm thiểu khoảng cách hamming sau các hoạt động hoán đổi bằng Python

Giả sử chúng ta có hai mảng số nguyên, src và tgt, cả hai đều có cùng độ dài. Chúng ta cũng có một mảng allowSwaps trong đó allowSwaps [i] chứa một cặp (ai, bi) chỉ ra rằng chúng ta có thể hoán đổi các phần tử tại chỉ mục ai với chỉ mục phần tử bi của mảng src. (Chúng tôi có thể hoán đổi các phần tử tại một cặp chỉ số cụ thể bao nhiêu lần tùy thích theo bất kỳ thứ tự nào). Như chúng ta đã biết khoảng cách Hamming của hai mảng có cùng độ dài, src và tgt, là số vị trí mà các phần tử khác nhau. Chúng ta phải tìm khoảng cách Hamming tối thiểu của src và tgt sau khi thực hiện bất kỳ số lượng hoạt động hoán đổi nào trên mảng src.

Vì vậy, nếu đầu vào giống như src =[2,3,4,5], tgt =[3,2,5,6], allowSwaps =[[0,1], [2,3]], thì đầu ra sẽ là 1 vì src có thể được chuyển đổi theo cách sau:Hoán đổi các chỉ số 0 và 1, vì vậy nguồn =[3,2,4,5], hoán đổi các chỉ số 2 và 3, vì vậy nguồn =[3,2,5,4] . Ở đây khoảng cách ẩn của src và tgt là 1 vì chúng khác nhau ở 1 vị trí:chỉ mục 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • graph:=một danh sách có kích thước giống như src và điền bằng n
  • Xác định một hàm find (). Điều này sẽ mất x
  • trong khi biểu đồ [x] không giống với x, hãy thực hiện
    • graph [x]:=graph [graph [x]]
    • x:=graph [x]
  • trả về x
  • Xác định một hàm union (). Điều này sẽ mất x, y
  • x1:=find (x), y1:=find (y)
  • đồ thị [x1]:=y1
  • Từ phương pháp chính, hãy thực hiện như sau
  • đối với mỗi cặp (x, y) trong Hoán đổi được phép, thực hiện
    • union (x, y)
  • groups:=một bản đồ trong đó các giá trị là danh sách, theo mặc định, danh sách trống
  • đối với tôi trong phạm vi từ 0 đến kích thước của src - 1, thực hiện
    • i1:=find (i)
    • chèn i vào cuối nhóm [i1]
  • ans:=0
  • đối với mỗi id trong danh sách tất cả các giá trị của nhóm, hãy thực hiện
    • counter:=một bản đồ trống để chứa các giá trị đếm
    • đối với mỗi idx trong id, hãy thực hiện
      • bộ đếm [src [idx]]:=bộ đếm [src [idx]] + 1
      • counter [tgt [idx]]:=counter [tgt [idx]] - 1
      • ans:=ans + (tổng của tất cả giá trị tuyệt đối của val, cho tất cả var trong danh sách các giá trị của bộ đếm) / 2
  • trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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

Đầu vào 

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

Đầu ra 

1