汉明立方体的数据结构

Question

我有一个普通尺寸的汉明立方体，但在实践中，尺寸通常在 3 到 6 之间。

搜索算法为：

Input: any vertex, `v`.
Find all vertices that lie in Hamming distance 1 from `v`.
Find all vertices that lie in Hamming distance 2 from `v`.
...

我事先不知道我需要离开 v 多远。例如，我可能会停在距离 1。

例如，给定这个立方体：

和 v = 100，我需要汉明距离为 1 的顶点，它们是 000、101、110（以任何顺序）。然后，我可能需要获取距离为 2 的顶点，即 111、001、010。万一也需要距离为 3 的顶点，我也会得到 011。

立方体的一个顶点可能包含 ID（整数）。

哪种数据结构适合存储此多维数据集并高效地搜索？我对其他操作不是很感兴趣。

我考虑过以某种方式对所有位序列进行排序，以便我可以轻松访问它们，但没有任何效果。

我目前的方法：

data-structure使用哈希表（特别是 std::unordered_map），其中键是顶点，值是 ID。

algorithm给定一个顶点 v，生成汉明距离 t 内的所有位序列（即 1、2、...）。

但是，这需要我在每次顶点v 到达时调用一个函数（这经常发生）。我有一个函数可以实现这个，基于 .

Answer 1

我对 C++ 生疏了，所以我将保持抽象。

您的汉明立方体给定点的邻居很容易计算。给定一个顶点的位序列，分别翻转每个位。

不过你可以预先计算一下。您可以缓存 neighbors() 函数的结果，或者可以将它们保存到一个数组中。每个顶点都有自己的邻居，因此每个顶点都有一个数组。这基本上为您提供了邻接列表。

使用该邻接表，您可以使用深度限制搜索来搜索您的汉明立方体，这是 DFS（我猜是 BFS，但 space 复杂性更差）的一种变体，它只会 k 个单位深。

你的数据结构是一个不错的选择，但考虑到你的顶点是二进制字符串，所以它们涵盖了从0到2^n - 1的所有点。您不妨只使用一个数组 — 查找仍然是 O(1)，而且它会更紧凑，因为周围没有未使用的桶。

Data structure for Hamming cube