三元矩阵的交集
Intersection of trinary matrices
考虑 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 个矩阵中的所有二进制字符串？
我认为最简单且相当有效的算法是暴力检查所有可能的组合。从 0000 开始，然后是 0001，然后是 0010 等等。使用它们中的每一个，迭代每个矩阵并比较值。在第一次匹配时，转到下一个矩阵，在不匹配时，立即拒绝。
您将不得不对每个矩阵最多迭代 16 次，这仍然是矩阵大小的 O(N)。
如果要优化实际比较，可以为每个矩阵预先计算查找字符串。为 0-allowed 和 1-allowed 创建反向位掩码，并将它们与查询字符串的 has-0 和 has-1 位掩码进行 AND 运算。如果两个结果中的任何一个不为零（您可以将它们相加或或并检查结果），则字符串将不匹配。
无论如何，对于任何类型的比较实现都应该非常快，因为您将只执行 16*(1000+1000+1000) 而不是您可能正在考虑的 (1000*1000*1000) 操作.
我们的想法是 "expand" 每一行都有其可能的集合，因此例如 1022 扩展为：
1000
1001
1010
1011
然后，将每个字符串转换为一个整数（一个单字节整数，因为 "strings" 是 4 位长）并放入一个排序数组，甚至一个集合中是很方便的。
下一步是按长度对组进行排序，从最小到最大，然后迭代最小的组值，看到它存在于所有其他组中，这非常快，因为[=中的准备工作21=]步.
通过所有组的每个值都是匹配项。
考虑 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 个矩阵中的所有二进制字符串？
我认为最简单且相当有效的算法是暴力检查所有可能的组合。从 0000 开始，然后是 0001，然后是 0010 等等。使用它们中的每一个，迭代每个矩阵并比较值。在第一次匹配时，转到下一个矩阵，在不匹配时，立即拒绝。
您将不得不对每个矩阵最多迭代 16 次，这仍然是矩阵大小的 O(N)。
如果要优化实际比较，可以为每个矩阵预先计算查找字符串。为 0-allowed 和 1-allowed 创建反向位掩码，并将它们与查询字符串的 has-0 和 has-1 位掩码进行 AND 运算。如果两个结果中的任何一个不为零（您可以将它们相加或或并检查结果），则字符串将不匹配。
无论如何，对于任何类型的比较实现都应该非常快，因为您将只执行 16*(1000+1000+1000) 而不是您可能正在考虑的 (1000*1000*1000) 操作.
我们的想法是 "expand" 每一行都有其可能的集合，因此例如 1022 扩展为：
1000
1001
1010
1011
然后，将每个字符串转换为一个整数（一个单字节整数，因为 "strings" 是 4 位长）并放入一个排序数组，甚至一个集合中是很方便的。
下一步是按长度对组进行排序，从最小到最大，然后迭代最小的组值，看到它存在于所有其他组中，这非常快，因为[=中的准备工作21=]步.
通过所有组的每个值都是匹配项。