arrays - 整数配列のサブセットが存在するかどうかを見つける効率的なアルゴリズム、そのすべての要素の xor が指定された値ですか?

Question

正の整数配列 {1,5,8,2,10} と特定の値 7 があります。要素の XOR が値 7 になるような配列のサブセットが存在するかどうかを調べる必要があります。この場合、 5 xor 2 は 7 であるため、サブセットは {5,2} です。単純な解決策の 1 つは、すべてのサブセットを見つけて、解決策が存在するかどうかを確認することです。単純なアルゴリズムよりも優れたアルゴリズムが必要です。注:-ソリューションが存在するかどうかを確認するだけで済みます。サブセットを見つける必要はありません。

Answer 1

これは、2 つの要素 (GF(2)) を持つ有限体上の線形方程式系を解くことに要約されます。ここでのビット単位の XOR は、2 つのベクトルを加算することと同じです。サンプル入力は、そのようなベクトルに対応します。

 1: 0001
 5: 0101
 8: 1000
 2: 0010
10: 1010
 7: 0111

システムはこんな感じ。

[0  0  1  0  1] [a]   [0]
[0  1  0  0  0] [b]   [1]
[0  0  0  1  1] [c] = [1]
[1  1  0  0  0] [d]   [1]
                [e]

次の Python コードは、ガウス消去法を使用し、ビット演算を使用して実装されています。固定幅整数の場合、線形時間で実行されます。ガウスの消去法については、既にインターネット上に 100 万の優れた処理方法があるにもかかわらず、再度説明していないことをお許しください。

#!/usr/bin/env python3
def least_bit_set(x):
    return x & (-x)


def delete_zeros_from(values, start):
    i = start
    for j in range(start, len(values)):
        if values[j] != 0:
            values[i] = values[j]
            i += 1
    del values[i:]


def eliminate(values):
    values = list(values)
    i = 0
    while True:
        delete_zeros_from(values, i)
        if i >= len(values):
            return values
        j = i
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) < least_bit_set(values[j]):
                j = k
        values[i], values[j] = (values[j], values[i])
        for k in range(i + 1, len(values)):
            if least_bit_set(values[k]) == least_bit_set(values[i]):
                values[k] ^= values[i]
        i += 1


def in_span(x, eliminated_values):
    for y in eliminated_values:
        if least_bit_set(y) & x != 0:
            x ^= y
    return x == 0


def main():
    values = [1, 5, 8, 2, 10]
    eliminated_values = eliminate(values)
    print(eliminated_values)
    x = int(input())
    print(in_span(x, eliminated_values))


if __name__ == '__main__':
    main()