โปรแกรมถอดรหัส permutation ที่ถูก XOR ใน Python

ได้รับอาร์เรย์ enc มีอาร์เรย์ perm เป็น permutation ของจำนวนเต็มบวก n ตัวแรก (n คี่) เข้ารหัสโดย enc[i] = perm[i] XOR perm[i+1] ต้องหา perm เดิม

ตัวอย่าง: enc=[2,5,6,3] ผลลัพธ์ [7,5,0,6,5]

วิธีแก้ปัญหา

1. n := len(enc), result := [0]*(n+1)
2. x := XOR ของ 1..n+1
3. result[0] := x
4. XOR enc[i] สำหรับ i คี่ (1,3,5...) เข้า result[0]
5. สร้าง result[i] = result[i-1] XOR enc[i-1]

ตัวอย่างโค้ด

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

อินพุต

[2,5,6,3]

เอาต์พุต

[7, 5, 0, 6, 5]