Chương trình tối thiểu hóa khoảng cách Hamming sau hoán vị cho phép trong Python

Mô tả bài toán

Cho mảng src, tgt cùng độ dài và allowedSwaps (cặp chỉ số có thể hoán vị không giới hạn lần). Khoảng cách Hamming = số vị trí khác nhau. Tìm khoảng cách Hamming tối thiểu sau các phép hoán vị cho phép.

Ví dụ

src = [2,3,4,5], tgt = [3,2,5,6], allowedSwaps = [[0,1],[2,3]] -> 1 (hoán vị 0-1 và 2-3 -> [3,2,5,4], khác tại chỉ số 3).

Giải thuật (Union-Find + Counter)

1. Dùng Union-Find gom nhóm các chỉ số có thể hoán vị lẫn nhau.
2. Với mỗi nhóm: đếm tần suất giá trị trong src và tgt.
3. Số vị trí khác nhau trong nhóm = sum(|cnt_src[v] - cnt_tgt[v]|) / 2.
4. Tổng cộng tất cả nhóm.

Triển khai Python

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))

Đầu vào

[2,3,4,5], [3,2,5,6], [[0,1],[2,3]]

Đầu ra

1