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

আমাদের দুটি ইন্টিজার অ্যারে আছে src এবং tgt, দুটোই একই দৈর্ঘ্যের। আমাদের আরও একটি অ্যারে আছে allowedSwaps যেখানে allowedSwaps[i] একটি জোড়া (ai, bi) ধারণ করে যা নির্দেশ করে আমরা src অ্যারেতে ইন্ডেক্স ai-এর এলিমেন্টকে ইন্ডেক্স bi-এর এলিমেন্টের সাথে সোয়াপ করতে পারি (আমরা একটি নির্দিষ্ট জোড়া ইন্ডেক্সে যেকোনো পরিমাণ সোয়াপ করতে পারি যেকোনো ক্রমে)। আমরা জানি দুটি একই দৈর্ঘ্যের অ্যারে src এবং tgt-এর হ্যামিং দূরত্ব হলো সেই পজিশনগুলোর সংখ্যা যেগুলোর এলিমেন্টগুলো ভিন্ন। আমাদের src-এ যেকোনো পরিমাণ সোয়াপ অপারেশন করার পর src এবং tgt-এর ন্যূনতম হ্যামিং দূরত্ব বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট src = [2,3,4,5], tgt = [3,2,5,6], allowedSwaps = [[0,1],[2,3]] হলে আউটপুট হবে 1 কারণ src-কে নিচেরভাবে রূপান্তর করা যায়: ইন্ডেক্স ০ এবং ১ সোয়াপ করলে src = [3,2,4,5], ইন্ডেক্স ২ এবং ৩ সোয়াপ করলে src = [3,2,5,4]। এখানে src এবং tgt-এর হ্যামিং দূরত্ব ১ কারণ সেগুলো ১টি পজিশনে ভিন্ন: ইন্ডেক্স ৩।

সমাধানের ধাপসমূহ (ইউনিয়ন-ফাইন্ড + ফ্রিকোয়েন্সি কাউন্ট)

• graph := src-এর আকারের লিস্ট n দিয়ে ফিল করে

• find(x) ফাংশন ডিফাইন করুন:

  • graph[x] != x থাকাকালীন: graph[x] = graph[graph[x]], x = graph[x]

  • x রিটার্ন করুন

• union(x, y) ফাংশন ডিফাইন করুন:

  • x1, y1 := find(x), find(y)

  • graph[x1] := y1

• মূল মেথড থেকে:

• allowedSwaps-এর প্রতিটি জোড়া (x, y) এর জন্য union(x, y)

• groups := ডিফল্টডিক্ট(লিস্ট)

• i = 0 থেকে src-এর আকার - 1 পর্যন্ত লুপ চালান: groups[find(i)].append(i)

• ans := 0

• groups-এর প্রতিটি ids এর জন্য:

  • counter := একটি খালি ম্যাপ

  • ids-এর প্রতিটি idx এর জন্য:

    • counter[src[idx]] += 1, counter[tgt[idx]] -= 1

  • ans += sum(abs(val) for val in counter.values()) / 2

• ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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