algorithm - 三元矩阵的交集

Question

考虑 3 个二元变量矩阵 b0,b1,b2,b3。所有这些矩阵具有相同的列数，但可以具有不同的行数。矩阵的每个元素可以具有三个值 1、0 或 2，其中 2 表示不关心。我必须找到所有三个矩阵中都存在的二进制字符串。例如，考虑以下 3 个矩阵:

matrix1:
1 0 2 2
2 2 0 0
1 2 1 1

matrix2:
2 2 0 2
1 0 1 2

matrix3:
2 2 1 2
1 2 2 1
2 2 2 1

因此，对于此示例，字符串 b0=1,b1=0,b2=1,b3=1 存在于所有矩阵中。因为，在matrix1中，b0=1,b1=2,b2=1,b3=1与1011相同。在matrix2中，b0=1,b1=0,b2=1,b3=2与1011相同，在matrix3中，b0=2,b1=2,b3=2,b3=1 与 1011 相同。

如何查找所有 3 个矩阵中存在的所有二进制字符串？

Answer 1

这个想法是将每一行“扩展”为其可能性的集合，例如 1022 扩展为:

1000
1001
1010
1011

然后，可以方便地将每个字符串转换为整数(单字节整数，因为“字符串”有 4 位长)并放入排序数组，甚至是集合中。

下一步是按长度从最小到最大对组进行排序，然后迭代最小的组值并查看它是否存在于所有其他组中，由于“解析”步骤中的准备工作，这非常快.

传递给所有组的每个值都是匹配的。