पायथन में स्वैप संचालन के बाद हैमिंग दूरी को कम करने का कार्यक्रम

मान लीजिए कि हमारे पास दो पूर्णांक सरणियाँ हैं, src और tgt, दोनों समान लंबाई के हैं। हमारे पास एक सरणी अनुमत स्वैप भी है जहां अनुमत स्वैप [i] में एक जोड़ी (एआई, द्वि) शामिल है जो इंगित करता है कि हम सरणी स्रोत के तत्व सूचकांक द्वि के साथ सूचकांक एआई पर तत्वों को स्वैप कर सकते हैं। (हम किसी भी क्रम में जितनी बार चाहें इंडेक्स की एक विशिष्ट जोड़ी पर तत्वों को स्वैप कर सकते हैं)। जैसा कि हम जानते हैं कि एक ही लंबाई, src और tgt के दो सरणियों की हैमिंग दूरी, उन पदों की संख्या है जहां तत्व भिन्न होते हैं। सरणी src पर किसी भी स्वैप ऑपरेशन को करने के बाद हमें src और tgt की न्यूनतम हैमिंग दूरी का पता लगाना होगा।

इसलिए, यदि इनपुट src =[2,3,4,5], tgt =[3,2,5,6], अनुमत स्वैप =[[0,1], [2,3]] जैसा है, तो आउटपुट 1 होगा क्योंकि src को निम्न तरीके से परिवर्तित किया जा सकता है:स्वैप इंडेक्स 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]
• रिटर्न x
• फ़ंक्शन को परिभाषित करें Union() । इसमें x, y लगेगा
• x1:=ढूंढें(x), y1:=ढूंढें(y)
• ग्राफ[x1] :=y1
• मुख्य विधि से, निम्न कार्य करें
• अनुमत स्वैप में प्रत्येक जोड़ी (x, y) के लिए, करें
  • संघ(x, y)
• समूह:=एक नक्शा जहां मान सूचियां हैं, डिफ़ॉल्ट सूचियां खाली हैं
• i के लिए 0 से src -1 के आकार के लिए, do
  • i1:=ढूंढें(i)
  • समूहों के अंत में i डालें[i1]
• उत्तर:=0
• समूहों के सभी मूल्यों की सूची में प्रत्येक आईडी के लिए, करें
  • काउंटर:=गिनती मान रखने के लिए एक खाली नक्शा
  • आईडी में प्रत्येक idx के लिए, करें
    • काउंटर[src[idx]] :=काउंटर[src[idx]] + 1
    • काउंटर[tgt[idx]] :=काउंटर[tgt[idx]] - 1
    • Ans :=ans + (वैल के सभी निरपेक्ष मान का योग, काउंटर के मानों की सूची में सभी 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