高效的算法来找到一个整数数组的一个子集是否存在，它的所有元素的异或为给定值？ [英] Efficient algorithm to find whether a subset of an integer array exists,the xor of all its elements is a given value?

问题描述

我有一个正整数阵列 - {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()

这篇关于高效的算法来找到一个整数数组的一个子集是否存在，它的所有元素的异或为给定值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！