用于在进行选择时动态查找允许的子集的算法/数据结构

Question

我正在开发一个显示用户输入表单的应用程序。该表单有 N 个部分，每个部分有 X 个单选按钮。提供了有效选择的子集，以便用户跨部分工作时，其他部分中的按钮将根据形成有效子集的可能性启用/禁用。

例如:第 1 部分有用于选择 A、B 和 C 的单选按钮第 2 部分有用于选择 1、2、3 和 4 的按钮第 3 部分有用于选择 x、y 和 z 的按钮

有效的子集是 ({A,2,z},{B},{B,1,x},{C,4}用户可以从任何部分开始选择，但我必须根据选择动态禁用按钮。

对于上面的示例，如果用户以 2 开头，我将只启用 A 和 z(也将启用 2)。我将无法使用 trie，因为它假设前缀匹配的输入顺序。是否有我可以用于此的数据结构？

Answer 1

您可以使用类似容器的位集来存储启用单选按钮。如果您使用的是 C++，则可以使用 std::bitset 如果大小在编译时已知，或者 boost::dynamic_bitset 如果不是。如果您使用的是其他语言，很可能在他们的库中已经有一个类似的容器，如果没有，您可以使用 int 的集合(根据单选按钮需要多少 int)来手动实现。

单选按钮只需要存储一个bitset(如果这个单选按钮存在于多个有效子集中，它们的bitset就是按位或 包含 的所有子集，表示只有这个单选按钮是检查bitset中指示的单选按钮是否有效。

当您选择任何第二个单选按钮时，您在实际事件的单选按钮位集和新选择的事件选项的位集之间执行按位与检查单选按钮有(预先计算)。这意味着只有至少一个子集中的单选按钮与所有先前选择的单选按钮处于事件状态。

例子:假设单选按钮是:A、B、C、1、2、3、4、x、y 和 z 它们在哪个部分是相同的。

使用有效集:({A,2,z},{B,2,z},{B},{B,1,x},{C,4}) 和 bitsets(每个单选按钮一位):

A: 1000100001   B: 0101100101    C: 0010001000
1: 0101000100   2: 1100100001    3: 0000010000    4: 0010001000
x: 0101000100   y: 0000000010    z: 1100100001

当已知有效子集并存储直到不再使用它们时，可以预先计算此位集。

您将从 1111111111 开始，全部启用，您的应用程序将检查此变量并根据此启用或禁用单选按钮。

当您选择 2 时，事件单选按钮将为 1111111111 和 1100100001 = 1100100001，您更新单选按钮状态(仅启用 A、B、 2 和 z)。如果您随后选择 A，则 1100100001 和 1000100001 = 1000100001。 (仅启用 A、2 和 z)。

bitset 可以存储在数组或列表或数组中(一个部分)，这样更容易编程。