Chương trình giải mã hoán vị XOR trong Python

Mô tả bài toán

Cho mảng enc. Mảng perm là hoán vị của n số nguyên dương đầu tiên (n lẻ). Mã hóa: enc[i] = perm[i] XOR perm[i+1]. Khôi phục perm.

Ví dụ

enc = [2,5,6,3] -> perm = [7, 5, 0, 6, 5].

Giải thuật

1. Tính x = XOR(1..n+1) (vì perm là hoán vị 1..n+1).
2. result[0] = x XOR (enc[1] XOR enc[3] XOR ...) (XOR các vị trí lẻ của enc).
3. Khôi phục lần lượt: result[i] = result[i-1] XOR enc[i-1].

Triển khai Python

def solve(enc):
    n = len(enc)
    result = [0] * (n + 1)
    x = 0
    for i in range(1, n + 2):
        x ^= i
    result[0] = x
    for i in range(1, n + 1, 2):
        result[0] ^= enc[i]
    for i in range(1, n + 1):
        result[i] = result[i-1] ^ enc[i-1]
    return result

enc = [2, 5, 6, 3]
print(solve(enc))

Đầu vào

[2,5,6,3]

Đầu ra

[7, 5, 0, 6, 5]