我有一个正整数阵列 - {1,5,8,2,10}和给定值7。 我需要找到数组的一个子集,是否存在这样的元素的XOR是值7。 在这种情况下,子集是{5,2},因为5异或2为7。 一个天真的解决办法是找到所有的子集和测试解决方案exist.I是否需要某种算法比天真好。 注:-I只需要找到一个解决方案是否存在not.I不需要找子集
I have a positive integer array- {1,5,8,2,10} and a given value 7. I need to find whether a subset of the array exists such that the XOR of its elements is the value 7. In this case the subset is {5,2} because 5 xor 2 is 7. One naive solution is to find all the subsets and check whether a solution exist.I want some algorithm better than the naive. NOTE:-I just need to find whether a solution exists or not.I don't need to find the subset.
这可以归结为求解线性方程组的系统在有限的领域有两个元素(GF(2))。按位XOR这里等效于将两个向量。样本输入对应的载体,像这样。
This boils down to solving a system of linear equations over the finite field with two elements (GF(2)). Bitwise XOR here is equivalent to adding two vectors. The sample inputs correspond to vectors like so.
1: 0001
5: 0101
8: 1000
2: 0010
10: 1010
7: 0111
该系统看起来是这样的。
The system looks like this.
[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 code使用高斯消元并使用位运算来实现。对于固定宽度的整数,它以线性时间运行。请原谅,我不能重解高斯消元时,有在互联网上万元的更好的治疗了。
The following Python code uses Gaussian elimination and is implemented using bitwise operations. For fixed-width integers, it runs in linear time. Forgive me for not reexplaining Gaussian elimination when there are a million better treatments on the Internet already.
#!/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()