找到唯一二元向量个数的有效解决方案

Question

假设你有一个长度为n的二进制向量(每个元素可以是0，1或X，对应于0或1)。

例如，给定N=4：

1001是单个二进制向量1XX1表示四个不同的二进制向量{1001，1011，1101，1111}

现在假设你有三种不同的描述，例如

X11X 1XX1 11XX

找到这组规范描述的唯一二进制向量的数量的有效解决方案是什么？

请注意，当N增长时，蛮力解决方案变得不切实际，因此列出所有可能的向量并删除重复项不是可行的解决方案。还请注意，我们只想知道唯一向量的数量，但不需要计算它们的确切值。

使用此示例的解决方案进行编辑，该解决方案为:

X11X -

1XX1 -

11XX --

在这12个向量中，我们只想计算唯一的向量，即8个。

0110 0111 1110 1111 1001 1011 1101 1100

Answer 1

如果模式数量保持较小，则可以使用包含-排除类型方法解决此问题。

每个模式的二进制向量的数量很容易计算:它正好是2的适当幂。现在，模式的总数就是每个模式的二元向量的和，减去每对模式的公共解的二元向量的数量，加上每个三元组的公共解的数量，等等。

集合模式的常见解再次是单个模式的解决方案：如果在某个位置，一个模式具有 0，而另一个模式具有 1，则没有公共解决方案。否则，如果其中一个形态在此位置处有 0 或 1，则我们通过将 0 或 1 放在某个位置来获得形态，如果所有形态在此位置都有 X，则为 X。

Answer 2

我会使用包含排除原则。您想知道集合的并集的基数。对于您的示例，您有：

N(X11X || 1XX1 || 11XX) = N(X11X) + N(1XX1) + N(11XX) - 
                          N(X11X && 1XX1) - N(X11X && 11XX) - N(1XX1 && 11XX) +
                          N(X11X && 1XX1 && 11XX)

“单个”元素的基数很容易计算（2^Nx，其中Nx是X元素的数量）。对于交点，逐个元素进行比较。如果它们与X不同，并且彼此不同，则为零。如果两者都相等，则为1。如果有一个X和一个数字，则为一。如果你有X和X，你就有两个。然后将这些数字相乘。例如：

N(X11X && 1XX1) = 1 * 1 * 1 * 1 = 1.

对应于唯一的公共序列（1111）。这可以很容易地推广到任何N，并且应该不难在任何语言中实现。