algorithm - 计算累积 XOR 小于 k 的子集数

Question

给定一个大小为 N 的集合 S。计算 S 的所有子集，其中子集的元素的累积 XOR 小于 K。

我可以想到蛮力方法来生成 S 的所有子集并计算累积 XOR 元素小于 k 的子集。我正在寻找优化的解决方案而不生成 S 的所有子集，我可以找到所有这样的子集

Example: 
S = {1,2}
K = 4
U = {{},{1},{2},{1,2}}
Answer is 4 As 
cumulative XOR values are 0 for {}, 1 for {1}, 2 for {2}, 3 for {1,2}.

Answer 1

根据问题的限制，有几种可行的方法来解决它:

• 正如您所指出的，如果 N 足够小，则尝试 O(2^N) 中所有可能的子集将产生预期的结果。
• 如果 S 中的值受一些足够小的值限制，您可以使用士官长的帖子中概述的动态规划解决方案。
• 如果 N 都很高，并且 S 中的值很大(十亿及以上)，则可以应用更复杂但多项式时间的方法。提纲如下:

让我们看一下 S 中数字的二进制表示，例如数字 17、5、20、14 将是:

10001 17
00101  5
10100 20
01110 14

对于 K 也一样，例如让我们取 K=11: 01011 11

如果我们想计算有多少子集与恰好 K 异或，我们可以将问题表示为一个模 2 的线性方程组，其中的变量与 S 中的数字一样多，并且许多方程式，因为我们的数字中有有意义的位。更具体地说，让第 i 个等式表示约束“S 的子集中第 i 位数字的 XOR 应等于 K 中的第 i 位”。 (请注意，XOR 运算等效于求和模 2)。例如，对于最小(最右边)的位，我们有以下内容:x1 * 1 + x2 * 1 + x3 * 0 + x4 * 0 = 1 (mod 2) ，其中 x_j 为 0 或 1，具体取决于我们是否在子集中包含第 j 个数。

请注意，这个方程组可能有 0 个、1 个或多个解。在多解的情况下，每个自变量可以取0或1，因此解的个数为2^(自变量)。

我们可以使用在 O(n^3) 中运行的高斯消元检测线性方程组的自变量数量和可解性对于大小为 n 的方阵- 在你的情况下，矩阵不是正方形的，所以我们可以使用 (|S|, log(max(S)) 中较大的一个估计复杂性。

太好了，现在我们可以遍历从 0 到 K-1 的所有 K' ，分别解决问题，并对结果求和。然而，这并不比动态规划解决方案更好，而且在运行时只是伪多项式。让我们进行另一个将产生多项式解的观察:我们只对 O(logK) 感兴趣不同的方程组计算有多少子集 XOR 小于 K .

让我们表示 K 中的最高非零位位置作为 B。如果 B 以上的所有位和 B 位在我们采用的子集的 XOR 中都等于 0，那么显然它将小于 K。 .因此，我们的第一个方程组可以只写出上述位，而忽略 B 以下的所有内容。

现在让我们看看如果我们允许第 B 位等于 1 会发生什么。如果在数字 K 中在第 B 个位置之后有一个或多个零位，它们在结果 XOR 中也必须全部为 0。如果第一个后续非零位 B2 在我们的 XOR 中设置为 0，那么它将小于 K。我们可以将此观察编码为第二个方程组，说“B 以上的所有位都是 0，位 B 是1，B和B2之间的位全部为0，B2位为0"，计算其解的个数。

如果我们继续这样直到 K 中的最小二进制位置, 我们最多需要构建 logK方程组，得到我们想要的结果。

这种方法的复杂度类似于 O(logK * max(n, logK)^3) ，尽管根据实现方式，高斯消去法对于非方矩阵的工作速度要快得多。