用 Python 编写程序来查找解码 XORed 排列

pythonserver side programmingprogramming更新于 2025/12/9 17:16:17

假设我们有一个数组 enc。有一个数组 perm，它是前 n(奇数)个正整数的排列。此列表将被编码为长度为 n-1 的数组 enc，这样 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]

为了解决这个问题，我们将遵循以下步骤 −

n := enc 的大小
result := 大小为 (n+1) 的数组并用 0 填充
x := 0
对于范围为 1 到 n+1 的 i，执行
- x := x XOR i
result[0] := x
对于范围中的 i 1 到 n，增加 2，执行
- result[0] := result[0] XOR enc[i]
对于 1 到 n 范围内的 i，执行
- result[i] := result[i-1] XOR enc[i-1]
返回 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))