arrays - 你如何找到异或为零的整数数组的最大子集

Question

澄清一下，数组的最大子集:[0,1,4,5,6,8] 与 0 的异或将是 [0,1,4,5]，因为 0^1^4^5= 0(其中 ^ 是异或)。我知道这可以通过蛮力在指数时间内完成，但我想知道下限是多少，以及当时用什么算法解决它。

我正在执行 Rational 筛选算法。超越wikipedia article ，关于算法的资源相当稀缺。要完成有理筛法，您会尝试找到一组数组的子集，以便在将相应元素相加时，生成的数组只有偶数。例如:

[2,3,4,5]+[4,3,4,3]=[6,6,8,8] 这将是一个有效的解决方案，前提是这些数组存在于更大的集合中。

根据那篇维基百科文章，这可以用线性代数来解决，但我不知道足够的线性代数来解决它。

为了算法的目的，空子集没有用。

我通过说数组只能有 0 和 1 并将数组放入单个数字以便可以使用单个运算符计算总和来简化问题，但除此之外它们是同一个问题。

Answer 1

是的，它可以表述为线性优化问题。假设整数是 k位，并且有 n其中，您可以将它们表示为 k * n矩阵 A ，其中列代表整数，行 r列 n是 r整数的第 - 位 i .

然后整数的选择和异或可以表示为A * x , 其中x是大小为 n 的向量在选定整数的位置有 1-s。这必须超过 GF(2)，所以乘法是标准的，加法是 XOR。所以你正在解决 maximize(|x|)受制于 Ax = 0 .