นับจำนวนคู่กลับลำดับด้วยการเรียงลำดับแบบผสานที่ดัดแปลง

การผกผันคืออะไร

arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
    for j in range(i+1, len(arr)):
        if arr[i] > arr[j]:
            inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions))  # 2

# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}')  # 10 for [5,4,3,2,1]

วิธีตรงไปตรงมา O(n²)

def count_inversions_brute(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count += 1
    return count

print(count_inversions_brute([3, 1, 2]))   # 2
print(count_inversions_brute([5, 4, 3, 2, 1]))  # 10
print(count_inversions_brute([1, 2, 3, 4, 5]))  # 0
print(count_inversions_brute([2, 4, 1, 3, 5]))  # 3

แนวคิดสำคัญของการเรียงลำดับแบบผสาน

# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')

การนำการเรียงลำดับแบบผสานที่ปรับแก้แล้วไปใช้งาน

def count_inversions(arr):
    def merge_sort_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left,  left_count  = merge_sort_count(arr[:mid])
        right, right_count = merge_sort_count(arr[mid:])
        merged, cross_count = merge_count(left, right)
        return merged, left_count + right_count + cross_count
    
    def merge_count(left, right):
        result, count = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1
                count += len(left) - i  # all remaining in left are inversions
        result += left[i:] + right[j:]
        return result, count
    
    _, total = merge_sort_count(arr)
    return total

print(count_inversions([3, 1, 2]))        # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3

การติดตามการทำงานของอัลกอริทึม

def count_with_trace(arr):
    def ms(arr, depth=0):
        indent = '  ' * depth
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = ms(arr[:mid], depth+1)
        R, rc = ms(arr[mid:], depth+1)
        merged, cc = merge_c(L, R)
        print(f'{indent}merge({L},{R}) → cross={cc}')
        return merged, lc + rc + cc
    
    def merge_c(L, R):
        res, c, i, j = [], 0, 0, 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]: res.append(L[i]); i += 1
            else: res.append(R[j]); j += 1; c += len(L) - i
        return res + L[i:] + R[j:], c
    
    _, total = ms(arr)
    return total

print('Total inversions:', count_with_trace([2, 4, 1, 3]))

เหตุใดจึงนับการผกผันข้ามครึ่งได้ถูกต้อง

# Verification: compare with brute force on random arrays
import random

def count_brute(arr):
    n = len(arr)
    return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a, 0
        m=len(a)//2
        L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr)[1]

for _ in range(100):
    arr = random.choices(range(20), k=random.randint(1,10))
    assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')

การประยุกต์ใช้จำนวนการผกผัน

# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems

def kendall_tau(rank1, rank2):
    '''Count inversions where rank1 and rank2 disagree on relative order.'''
    # Map rank2 positions to create a comparison sequence
    pos = {v: i for i, v in enumerate(rank2)}
    # Convert rank1 to position-in-rank2 ordering
    arr = [pos[v] for v in rank1]
    return count_inversions(arr)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

print(kendall_tau([1,2,3],[3,1,2]))  # measures disagreement

ที่เกี่ยวข้อง: นับจำนวนที่น้อยกว่าหลังสมาชิกปัจจุบัน

def count_smaller(nums):
    n = len(nums)
    result = [0] * n
    indexed = list(enumerate(nums))
    
    def merge_sort(arr):
        if len(arr) <= 1: return arr
        mid = len(arr) // 2
        left  = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])
        return merge(left, right)
    
    def merge(left, right):
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i][1] <= right[j][1]:
                # left[i] is placed; j elements from right are smaller and to the right
                result[left[i][0]] += j
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
        while i < len(left):
            result[left[i][0]] += j  # all of right is smaller
            merged.append(left[i]); i += 1
        return merged + right[j:]
    
    merge_sort(indexed)
    return result

print(count_smaller([5, 2, 6, 1]))  # [2, 1, 1, 0]

คู่ย้อนกลับ

def reverse_pairs(nums):
    def merge_sort_count(arr):
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        L, lc = merge_sort_count(arr[:mid])
        R, rc = merge_sort_count(arr[mid:])
        # Count cross pairs: L[i] > 2*R[j]
        j = 0
        cross = 0
        for l_val in L:
            while j < len(R) and l_val > 2 * R[j]:
                j += 1
            cross += j
        # Normal merge (separate from count)
        merged = []
        i = jj = 0
        while i < len(L) and jj < len(R):
            if L[i] <= R[jj]: merged.append(L[i]); i += 1
            else: merged.append(R[jj]); jj += 1
        merged += L[i:] + R[jj:]
        return merged, lc + rc + cross
    
    return merge_sort_count(nums)[1]

print(reverse_pairs([1, 3, 2, 3, 1]))  # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3

เปรียบเทียบจำนวนอินเวอร์ชันแบบสากลกับแบบเฉพาะที่

def is_ideal_permutation(A):
    '''Global inversions == local inversions
    iff no element is more than 1 position from its sorted index.'''
    return all(abs(a - i) <= 1 for i, a in enumerate(A))

print(is_ideal_permutation([1, 0, 2]))  # True
print(is_ideal_permutation([1, 2, 0]))  # False (A[0]=1 is far from 2, A[2]=0 is far)

# Verification with inversion counts
print(count_inversions([1, 0, 2]))  # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1)  # 1 (equal)

def count_inversions(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

สรุปความซับซ้อนของจำนวนอินเวอร์ชัน

import time, random

def time_method(func, arr):
    start = time.time()
    result = func(arr[:])
    return result, time.time() - start

def count_brute(arr):
    return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])

def count_dc(arr):
    def ms(a):
        if len(a)<=1: return a,0
        m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
        res,c,i,j=[],0,0,0
        while i<len(L) and j<len(R):
            if L[i]<=R[j]: res.append(L[i]);i+=1
            else: res.append(R[j]);j+=1;c+=len(L)-i
        return res+L[i:]+R[j:],(lc+rc+c)
    return ms(arr[:])[1]

arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C:   {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทบทวนบทเรียน