在数组中查找N个元素，使它们的异或等于P。

Question

我正在解决一个问题，需要找出一个长度为小于20的数组中，有多少种组合使得它们的异或和等于P。

例如：给定数组{2 4 5 2 7}

1）如果N=2且P=6，则答案为2（因为只有(2 xor 4) = 6 和 (4 xor 2) = 6两种情况可选）

{2 4 5 2 7} 或 {2 4 5 2 7}

2）如果N=3且P=6，则答案为1（因为(4 xor 5 xor 7) = 6)

由于数组的规模可能非常大（约10^6），因此我在寻找一种快速解决该问题的算法。

- Mark

---

XOR 中允许重复数字吗？如果不允许，那么 N 只能和数组大小相同。 - OneCricketeer

你认为快速算法存在的原因是什么？显然并不存在任何多项式时间算法。 - John Coleman

嗯，我相信你可以将这个转化为一个具有整数系数的Z_2方程组。 - blazs

继@JohnColeman所说的，这个问题最多是固定参数可解的，因为去除N的限制允许从一个经典的#P完全问题（计数完美匹配）进行简单的约化。VtC太宽泛了，因为这是作业。 - David Eisenstat

有趣的事实是，6 xor (2 xor 4) = 0 和 6 xor (4 xor (5 xor 7)) = 0。也许这能帮到你？ - OneCricketeer

Answer 1

由于N是固定的，所以编辑无法工作

使用线性代数：

正如@blazs建议的那样，您可以将P和数组中的每个数字视为Z/2Z向量空间中的向量。更重要的是，由于XOR是结合律和交换律，因此您不是在寻找数组元素的组合，而是这些元素的集合，而集合也可以编码为Z/2Z向量。

因此，您最终会得到一个矩阵方程M*S=P，其中P是以Z/2Z向量格式表示的异或和，M是矩阵，其列是以Z/2Z格式表示的数组元素，而S是方程的未知数。

由于您只对解决方案空间的大小感兴趣，所以您需要做的就是找到解决方案空间的维度，然后将2提高到该维度的幂次方。

- Valentin Waeselynck

---

我两个小时前发布并删除了这个答案。它不起作用是因为子集中元素的数量N是固定的。 - David Eisenstat

@DavidEisenstat，我认为你可以将其设置为方程组Ax=y，同时要求||x||^2 = N？（虽然我还没有解决它...我可能会尝试在今天晚些时候这样做。） - blazs

一个人需要找到（生成）一个线性应用f和一个常向量C，使得当且仅当S的支集基数为N时，fS=C。我不知道这是否可能。 - Valentin Waeselynck

我确认这是不可能的。 - Valentin Waeselynck

不，如果我移除N个元素的限制，那么我可以在O（数组大小* P）的时间内计算子集数量。我的意思是，我们可以将变量P设置为所有元素的异或值的常量值。 - Mark

Answer 2

提出递归算法，可能比暴力算法更快：

找到P中为1的某个位。任何解决方案组合都必须包含至少一个在该位上具有1的数字。

对于数组的每个具有该位上为1的元素K，请使用以下递归：

• P' = P xor K （xor-减法）
• arr' = arr - {在该位上具有1且索引小于或等于K的J集合} （因为我们假设K是具有此位置上1的组合中的第一个元素）
• N = N - 1

终止情况：

• 如果P=0且N=0，则有一个解决方案
• 如果N=0且P！=0，则没有解决方案
• 如果arr为空，则没有解决方案
• 如果存在一个位，其中P具有1且arr的任何元素都没有，则没有解决方案

请注意，XOR是可结合和可交换的，因此我们计算的是集合而不是组合。

- Valentin Waeselynck

---

我也尝试了类似的递归方法，例如使用相同的基本终止情况 - 然而，我不确定第二步是什么，并且你在这里提到位的事实。请注意，每个位通过包含包含该位的奇数数量的元素来设置，并且每个位通过包含包含该位的偶数数量的元素来清除。我不确定这是否仍然涵盖在此处... - Marco13