पायथन में XORed परम्यूटेशन को डिकोड करने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे enc है। एक ऐरे perm है जो पहले n (ऑड) पॉजिटिव इंटीजर्स का परम्यूटेशन है। इस सूची को enc ऐरे में एन्कोड किया जाता है जिसकी लंबाई n-1 होती है, जैसे कि enc[i] = perm[i] XOR perm[i+1]। हमें मूल ऐरे perm ढूंढना है।

उदाहरण के लिए, यदि इनपुट enc = [2,5,6,3] है, तो आउटपुट [7, 5, 0, 6, 5] होगा, यहां [7 XOR 5 XOR 0 XOR 6 XOR 5] = [2, 5, 6, 3]।

हल करने के चरण

1. n := len(enc)
2. result := आकार (n+1) का ऐरे और 0 से भरें
3. x := 0
4. i को 1 से n+1 तक लूप चलाएं:
   • x := x XOR i
5. result[0] := x
6. i को 1 से n तक 2 से बढ़ाते हुए लूप चलाएं:
   • result[0] := result[0] XOR enc[i]
7. i को 1 से n तक लूप चलाएं:
   • result[i] := result[i-1] XOR enc[i-1]
8. result वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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]