PythonでXORエンコードされた配列から元の順列を復元するプログラム

長さ n(奇数)の配列 perm があり、これは最初の n 個の正整数を並べ替えた順列であるとします。この配列は、enc[i] = perm[i] XOR perm[i+1] という規則によって、長さ n-1 の配列 enc にエンコードされています。本記事では、エンコード後の配列 enc から元の配列 perm を復元する方法を解説します。

例として、入力が enc = [2,5,6,3] の場合、出力は [7, 5, 0, 6, 5] になります。実際に確認すると、隣接要素同士のXORは [7 XOR 5, 5 XOR 0, 0 XOR 6, 6 XOR 5] = [2, 5, 6, 3] となり、元の配列と一致します。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• n := enc のサイズ
• result := サイズ (n+1) の配列を用意し、0 で初期化する
• x := 0
• i を 1 から n+1 までループし、x := x XOR i を計算する
• result[0] := x とする
• i を 1 から n まで 2 ずつ増やしながら、result[0] := result[0] XOR enc[i] を計算する
• i を 1 から n までループし、result[i] := result[i-1] XOR enc[i-1] を計算する
• result を返す

なぜこのアルゴリズムで動くのか

このアルゴリズムの鍵となるのは、次の性質です。

1. 順列全体のXORは一意に決まる

perm は 1 から n+1 までの正整数の順列なので、全要素のXOR値は「1 から n+1 までの全整数のXOR」と必ず等しくなります。これが変数 x の計算に相当します。

2. 奇数インデックスの enc から先頭要素を分離できる

enc の奇数インデックス(1, 3, 5, …)の要素をすべてXORすると、perm[1] XOR perm[2]、perm[3] XOR perm[4]、… が得られます。全体のXORの中でペアにならずに残るのは perm[0] だけなので、次の式で先頭要素を求められます。

perm[0] = (1〜n+1 の総XOR) XOR (enc[1] XOR enc[3] XOR …)

3. 残りの要素は連鎖的に復元できる

enc[i-1] = perm[i-1] XOR perm[i] という定義から、result[i] = result[i-1] XOR enc[i-1] を繰り返し適用することで、残りの要素をすべて復元できます。

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

def solve(enc):
    n = len(enc)
    result = [0] * (n + 1)
    x = 0
    # 1 から n+1 までの総XORを計算
    for i in range(1, n + 2):
        x ^= i
    result[0] = x
    # 奇数インデックスの enc 要素で先頭要素を確定させる
    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]

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量も結果を格納するために必要な O(n) であり、非常に効率的に元の順列を復元できます。