PythonでデコードされたXOR順列を見つけるプログラム

配列encがあるとします。最初のn（odd）個の正の整数の順列である配列permがあります。このリストは、enc [i] =perm [i] XOR perm [i+1]のように長さn-1の配列encにエンコードされます。元の配列パーマを見つける必要があります。

したがって、入力が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
• 1からnの範囲のiの場合、2ずつ増やします。
  • result [0]：=result [0] XOR enc [i]
• 1からnの範囲のiについては、
  • 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]