পাইথনে সোয়াপ অপারেশনের পর হ্যামিং দূরত্ব কমানোর জন্য প্রোগ্রাম

ধরুন আমাদের দুটি পূর্ণসংখ্যা অ্যারে আছে, src এবং tgt, উভয়ই একই দৈর্ঘ্যের। আমাদের কাছে একটি অ্যারে অনুমোদিত সোয়াপ রয়েছে যেখানে অনুমোদিত সোয়াপস[i]-এ একটি জোড়া (ai, bi) রয়েছে যা নির্দেশ করে যে আমরা অ্যারে src-এর এলিমেন্ট ইনডেক্স bi-এর সাথে ইনডেক্স ai-তে উপাদানগুলিকে অদলবদল করতে পারি। (আমরা যেকোনো ক্রমে যতবার চাই ততবার সূচকের একটি নির্দিষ্ট জোড়ায় উপাদানগুলিকে অদলবদল করতে পারি)। যেমন আমরা জানি একই দৈর্ঘ্যের দুটি অ্যারের হ্যামিং দূরত্ব, 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 এর মতো নয়, do
  • গ্রাফ[x] :=গ্রাফ[গ্রাফ[x]]
  • x :=গ্রাফ[x]
• ফেরত x
• একটি ফাংশন ইউনিয়ন () সংজ্ঞায়িত করুন। এটি x, y
লাগবে
• x1 :=find(x), y1 :=find(y)
• গ্রাফ[x1] :=y1
• মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
• প্রতিটি জোড়ার জন্য (x, y) অনুমোদিত অদলবদল, করুন
  • ইউনিয়ন(x, y)
• গোষ্ঠী :=একটি মানচিত্র যেখানে মানগুলি তালিকা, ডিফল্ট তালিকাগুলি খালি থাকে
• আমি 0 থেকে src - 1 এর পরিসরের জন্য, do
  • i1 :=খুঁজুন(i)
  • গোষ্ঠীর শেষে i ঢোকান[i1]
• উত্তর :=0
• গ্রুপের সমস্ত মানের তালিকার প্রতিটি আইডির জন্য, করুন
  • কাউন্টার :=গণনা মান ধরে রাখার জন্য একটি খালি মানচিত্র
  • আইডিতে প্রতিটি আইডিএক্সের জন্য, করুন
    • কাউন্টার[src[idx]] :=counter[src[idx]] + 1
    • কাউন্টার[tgt[idx]] :=counter[tgt[idx]] - 1
    • উত্তর :=উত্তর + (ভ্যালের সমস্ত পরম মানের সমষ্টি, কাউন্টারের মানের তালিকায় সমস্ত 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