Inversion counting — குழப்பம்

Inversion — i < j ஆனாலும் a[i] > a[j]. இவற்றை எண்ணுவது தரவு எவ்வளவு தூரம் sorted-இலிருந்து விலகியுள்ளது என்று காட்டும்; merge sort உட்புறமாகவும் பயன்.

உண்மை உலகில் இது ஏன் முக்கியம்?

இசை வரிசை பட்டியல்களை ஒப்பிடும்போது inversion தூரம் மாறுபாட்டை எண்ணாக்குகிறது. பரிந்துரை இயந்திரங்கள் இரண்டின் வரிசை வேறுபாடு. merge கருவி முரண்பாடுகள் — வரிசை குழப்பத்தின் எண் பார்வை.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

சிறியதற்கு O(n²) இரட்டை வளையம். போட்டிக்கு merge sort: இணைக்கும்போது வலது R[j] ஐ எடுத்தால், இடது L இல் மீதமுள்ள ஒவ்வொன்றும் inversion — len(L)-i கூட்டு. O(n log n). “Reverse pairs” பிரச்சினைகள் இதே கட்டமைப்பு.

Pythonில் முயற்சி செய்வோம்

def merge_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cl = merge_count(a[:mid])
    right, cr = merge_count(a[mid:])
    merged, cm = merge(left, right)
    return merged, cl + cr + cm


def merge(left, right):
    i = j = inv = 0
    out = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            inv += len(left) - i
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:], inv


arr, k = merge_count([2, 4, 1, 3, 5])
print(k, arr)

அடிக்கடி நேரும் தவறுகள்

• எண்ணில் முழு எண் வெடிப்பு — Python int.
• merge இல் len(left)-i ஒற்றைப் பிழை.
• நகல்கள் — > vs >= வரையறை.

முக்கியச் சுருக்கக் குறிப்புகள்

• Inversions — permutation தூரம் பாணி.
• merge அடிப்படை O(n log n).
• சம மதிப்பு விதி எண்ணிக்கையை மாற்றும்.