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

मान लीजिए हमारे पास दो इंटीजर ऐरे, 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 को निम्न तरीके से बदला जा सकता है: इंडेक्स 0 और 1 को स्वैप करें, तो सोर्स = [3,2,4,5], इंडेक्स 2 और 3 को स्वैप करें, तो सोर्स = [3,2,5,4]। यहां src और tgt की हैमिंग दूरी 1 है क्योंकि वे 1 पोजीशन में भिन्न हैं: इंडेक्स 3।

हल करने के चरण

1. graph := src के आकार की सूची और n से भरें
2. find() फ़ंक्शन परिभाषित करें। यह x लेगा:
   • graph[x] != x तक व्हाइल लूप चलाएं:
     • graph[x] := graph[graph[x]]
     • x := graph[x]
   • x वापस करें।
3. union() फ़ंक्शन परिभाषित करें। यह x, y लेगा:
   • x1 := find(x), y1 := find(y)
   • graph[x1] := y1
4. मुख्य मेथड से, निम्नलिखित करें:
   • allowedSwaps में प्रत्येक जोड़ी (x, y) के लिए union(x, y) करें।
   • groups := एक मैप जहां मान सूचियां हैं, डिफ़ॉल्ट रूप से सूचियां खाली हैं
   • i को 0 से len(src) - 1 तक लूप चलाएं:
     • i1 := find(i)
     • i को groups[i1] के अंत में जोड़ें
   • ans := 0
   • groups के सभी मानों की सूची में प्रत्येक ids के लिए:
     • counter := काउंट मान रखने के लिए खाली मैप
     • ids में प्रत्येक idx के लिए:
       • counter[src[idx]] := counter[src[idx]] + 1
       • counter[tgt[idx]] := counter[tgt[idx]] - 1
       • ans := 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