โปรแกรมเพื่อลดระยะการกระแทกหลังจากดำเนินการสลับใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็มสองอาร์เรย์ src และ tgt ทั้งคู่มีความยาวเท่ากัน นอกจากนี้เรายังมีอาร์เรย์ที่ได้รับอนุญาตSwaps โดยที่ allowedSwaps[i] มีคู่ (ai, bi) บ่งชี้ว่าเราสามารถสลับองค์ประกอบที่ดัชนี ai กับองค์ประกอบดัชนี bi ของอาร์เรย์ src (เราสามารถสลับองค์ประกอบที่คู่ของดัชนีหนึ่งๆ ได้มากเท่าที่เราต้องการในลำดับใดก็ได้) ดังที่เราทราบระยะ Hamming ของสองอาร์เรย์ที่มีความยาวเท่ากัน src และ tgt คือจำนวนตำแหน่งที่องค์ประกอบต่างกัน เราต้องหาระยะแฮมมิงขั้นต่ำของ src และ tgt หลังจากดำเนินการสลับจำนวนเท่าใดก็ได้บนอาร์เรย์ src

ดังนั้นหากอินพุตเป็นเหมือน 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 ดังนั้น source =[3,2,5,4] . ระยะแฮมมิงของ src และ tgt คือ 1 เนื่องจากต่างกันใน 1 ตำแหน่ง:ดัชนี 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กราฟ :=รายการขนาดเท่ากับ src และเติมด้วย n
• กำหนดฟังก์ชัน find() นี่จะใช้เวลา x
• ในขณะที่กราฟ[x] ไม่เหมือนกับ x ให้ทำ
  • กราฟ[x] :=กราฟ[กราฟ[x]]]
  • x :=กราฟ[x]
• ผลตอบแทน x
• กำหนดฟังก์ชัน union() นี่จะใช้เวลา x, y
• x1 :=find(x), y1 :=find(y)
• กราฟ[x1] :=y1
• จากวิธีหลัก ให้ทำดังนี้
• สำหรับแต่ละคู่ (x, y) ใน allowSwaps ทำ
  • ยูเนี่ยน(x, y)
• groups :=แผนที่ที่มีค่าเป็นรายการ โดยค่าเริ่มต้นรายการจะว่างเปล่า
• สำหรับฉันในช่วง 0 ถึงขนาดของ src - 1 ทำ
  • i1 :=find(i)
  • ใส่ i ต่อท้ายกลุ่ม[i1]
• ตอบ :=0
• สำหรับแต่ละรหัสในรายการค่าทั้งหมดของกลุ่ม ทำ
  • ตัวนับ :=แผนที่ว่างเพื่อเก็บค่าการนับ
  • สำหรับแต่ละ idx ใน id ให้ทำ
    • ตัวนับ[src[idx]] :=ตัวนับ[src[idx]] + 1
    • ตัวนับ[tgt[idx]] :=ตัวนับ[tgt[idx]] - 1
    • ans :=ans + (ผลรวมของค่าสัมบูรณ์ทั้งหมดของ val สำหรับ var ทั้งหมดในรายการค่าของตัวนับ)/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