寻找满足特定条件的子集

Question

我有几个数字数组（每个数组的元素只能取0或1），如下：

v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

我希望找到这样的子集，使得当这些数组相加时，所得到的结果数组中的每个元素都是2的倍数。例如，v1+v2+v3可以得到一个结果数组为2, 2, 0, 2, 2。结果数组可以是任何2的倍数。

另一个例子：

v1: 1, 1, 1, 0, 1, 0
v2: 0, 0, 1, 0, 0, 0
v3: 1, 0, 0, 0, 0, 0
v4: 0, 0, 0, 1, 0, 0
v5: 1, 1, 0, 0, 1, 0
v6: 0, 0, 1, 1, 0, 0
v7: 1, 0, 1, 1, 0, 0

在这个例子中，v1+v2+v5和v3+v6+v7是合适的答案。

我有一个暴力解决方案，但我想检查是否有更有效的方法。这与子集求和问题等价吗？

- Neo

---

能否详细说明： 1）集合有多长？ 2）您需要结果总和数组吗？ - Eugen Rieck

程序开始时，每个数组中的元素数量和这样的数组的数量都是未知的。实际上，我不需要求和数组，只需要知道数组的数量。因此，如果v1+v2+v5是结果，则我需要知道1、2、5。 - Neo

@Banthar 哇..高斯消元确实似乎是正确的做法。我只需要找到所有可能的Vx=0的解，其中V是包含我所有数组的矩阵。我认为x会给我相应的行数。 - Neo

关于高斯-约旦消元法：请记住，在每个维度中，x被限制为0/1；而且你要寻找的是“=0 mod 2”，而不是“=0”，同样在每个维度中（这与将其视为应用于Vx的任何范数的“=0 mod2”不同）。 - gnometorule

@Neo，高斯消元对你有用吗？如果是的话，你能把它发布为答案并接受吗？ - dsolimano

我实际上没有跟进解决方案，因为我还有其他事情要做。正如@gnometorule所提到的，所需的操作是0模2，并且我也一直对高斯-约旦方法返回的解的数量存在疑虑。如果我将来再次着手解决此问题，我肯定会发布我的解决方案。 - Neo

Answer 1

你想找到所有的解决方案还是只找一个？

这个方法可以找到一个解决方案（我认为可能可以扩展它以找到所有的解决方案）。

将每个数组表示为二进制数。

所以v1变成10011，v2变成01001等等。

让*表示按位模2加法。

例如：

v1*v2*v3 = 00000

因此，我们的目标是找到其模2加法为零的数组。

让u和v是任何二进制数。

那么当且仅当u = v时，u * v = 0。

例如：

(v1*v2)*v3 = 0
v1*v2 = 11010 = v3.

如果u*v = w

u*v*v = w*v, so
u*0 = w*v,
u = w*v

因此，我们可以从0开始进行反向搜索。假设最终的数组集合包含v。那么v*T = 0，其中T是某个二进制数。我们有T = 0*v。如果T是给定的数组之一，那么我们就完成了。否则，我们将从T开始继续搜索。

以下是正式描述：

每个状态都是一个二进制数。

让0成为初始状态。

给定的数组是状态空间的某个子集，称为S。

我们的目标状态是S中的任何元素。

让T成为所需的数组子集，其总和为0。

在每个状态下，让可能的操作是*，与不在T中的任何状态。

在每个操作后，放置用于T的数组。

如果在任何非目标阶段S = T，则没有解决方案。

现在，我们可以在这个空间上运行DFS来找到解决方案。

- Jayanth Koushik