c++ - 如何快速检查(非平凡的)数字列表的等价性？

Question

我有一个整数列表，例如 1,2,2,3,4,1。我需要能够检查不同列表之间的等价性 (==)。

但是，我并不是指简单的数字比较。这些列表中的每一个实际上表示一个集合分区，其中列表中的位置表示元素的索引，数字表示组的索引。例如，在前者中，元素 0 和元素 5 在同一组中，元素 1 和元素 2 在同一组中，元素 3 和 4 都在各自的组中。 分组的实际索引并不重要，重要的只是分组。

我需要能够在这个意义上测试等价性，例如，前面的列表等价于 5,3,3,2,9,5,，因为它们具有相同的分组.

我一直这样做的方法是将数组简化为一种正常形式。我发现所有数字都与第一个数字具有相同的值，并将它们全部设置为 0。 然后我继续在列表中直到找到一个新数字，找到所有具有相同值的数字并将它们全部设置为 1。我以这种方式继续。

在我的示例中，两个数字都会减少到 0,1,1,2,3,0，当然我可以使用简单的比较来查看它们是否等价。

但是这很慢，因为我必须对列表进行多次线性传递。因此，切入正题，是否有更有效的方式将这些数字减少到这种正常形式？

但是，更一般地说，我能否一起避免这种缩减，并以不同且可能更有效的方式比较数组？

实现细节

• 这些数组实际实现了 作为 bitsets 以节省空间，所以我真的每次都必须遍历整个列表，因为没有 rb_tree esque 哈希正在进行。
• 大 这些阵列的数量将是 存储在 STL unordered_set 中，因此 应考虑对哈希的要求

Answer 1

尝试并行遍历两个序列，保留从第一个数组中的值到第二个数组中的值的映射(std::map 或数组)，反之亦然。如果你得到一对不在你的表中，添加它，除非表中有第一个或第二个数字的东西(因为这表明不平等)。例如:

1,2,2,3,4,1
5,3,3,2,9,5

您可以添加 1->5、2->3、3->2 和 4->9，比较就会通过。对于稍微不同的东西:

5,3,3,2,9,5
1,2,2,3,2,1

您将添加 5->1、3->2、2->3，然后 9->2 将失败，因为在第二个序列中已经有 2 的绑定(bind)；因此，您会知道这些序列是不等价的。

要创建散列函数，您可能需要执行您正在执行的规范化，但它应该只需要遍历序列一次。同样，保持两个方向的映射，但如果您在输入序列中找到未知元素，请将其映射到下一个可用数字，否则使用映射将输入序列转换为规范化序列。