arrays - 查找整数数组的子集是否存在的有效算法，其所有元素的异或是否为给定值？

Question

我有一个正整数数组 - {1,5,8,2,10} 和给定值 7。我需要查找数组的子集是否存在，使得其元素的 XOR 值为 7。在这种情况下子集是 {5,2} 因为 5 xor 2 是 7。一个天真的解决方案是找到所有子集并检查是否存在解决方案。我想要一些比天真的算法更好的算法。注意：-我只需要找到解决方案是否存在。我不需要找到子集。

Answer 1

这归结为求解具有两个元素 (GF(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 代码使用高斯消元法，并使用按位运算实现。对于固定宽度的整数，它以线性时间运行。当互联网上已经有一百万种更好的治疗方法时，请原谅我没有重新解释高斯消除。

#!/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()