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

दो सूचियाँ L1 और L2 दी गई हैं, दोनों की लंबाई n है और प्रत्येक में 1 से n तक के अद्वितीय मान हैं। L1 को L2 में बदलने के लिए आवश्यक न्यूनतम आसन्न स्वैप की संख्या ढूंढें।

उदाहरण

इनपुट: L1 = [0, 1, 2, 3], L2 = [2, 0, 1, 3]

आउटपुट: 2

चरण: 1 और 2 स्वैप करें → [0, 2, 1, 3], फिर 0 और 2 स्वैप करें → [2, 0, 1, 3]।

मुख्य अंतर्दृष्टि

आसन्न स्वैप की न्यूनतम संख्या = L2 के तत्वों को L1 में उनके सूचकांकों द्वारा प्रतिस्थापित करके बने क्रमपरिवर्तन का इनवर्जन काउंट (inversion count) है। लेकिन एक सरल लालची दृष्टिकोण काम करता है:

1. L2 के प्रत्येक तत्व req के लिए (बाएं से दाएं):
• L1 में req का सूचकांक i ढूंढें।
• L1 से i-वें तत्व को हटाएं (यह अनुकरण करता है कि हम इसे सामने लाने के लिए i आसन्न स्वैप करते हैं)।
• ans += i।

पायथन कार्यान्वयन

class Solution:
    def solve(self, L1, L2):
        ans = 0
        for req in L2:
            i = L1.index(req)  # सूचकांक ढूंढें
            L1.pop(i)          # हटाएं
            ans += i           # स्वैप जोड़ें
        return ans

# परीक्षण
ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))  # 2

समय जटिलता

• O(n²) क्योंकि list.index() और list.pop(i) दोनों O(n) हैं।
• बड़े n के लिए, फेनविक ट्री (BIT) का उपयोग करके इनवर्जन काउंट O(n log n) में निकालें।

फेनविक ट्री अनुकूलन (संक्षिप्त)

def min_swaps_fenwick(L1, L2):
    pos = {val: i for i, val in enumerate(L1)}
    perm = [pos[val] for val in L2]
    # perm का इनवर्जन काउंट गिनें BIT से
    # ...