sorting - 有序格点枚举

Question

设置：设 ei 是 n 维欧几里得空间的正交基，但假设 ei 具有无理 (L1) 范数。令 L 为通过将 ei 与自然数（包括零）的系数进行线性组合而获得的点集​​。现在首先按 L1 范数对 L 中的点进行排序，然后按字典顺序排列。

问题：是否有一种有效的算法可以按递增顺序生成 L 中的点，直到某个预定义的界限？请注意，我不想产生点然后对它们进行排序，而是想按顺序走格子。

观察：如果 ei 是标准正交基，这很容易做到。例如，这个问题在这里解决。原则上类似的东西在这里会起作用，但是确定要迭代的半径几乎和解决枚举问题一样难，所以它不是很有用。

Answer 1

这个怎么样：

令 L1 和 L2 是向量列表，其中 L1 是已访问/已处理的格向量列表，L2 是接下来要访问的向量列表。

1. 设置 L₁={ } 和 L₂ = {[0]}，其中 0 是零向量。
2. 令 v 为 L₂ 中第一个列表的最小向量。
3. 访问/处理向量 v。
4. 将列表 L={v+e₁,...,v+e _n } 添加到 L₂，以便列表按其最小元素排序。只生成 v+e _i只要其范数小于您的预定义界限。
5. 在 L1 的末尾插入 v 并将其从第一个列表 L2 的前面删除。
6. 如果第一个列表现在为空，请将其从 L₂ 中删除。如果没有，请将其移动到正确的位置。
7. 如果 L₂ 不为空，则转到 2。

该算法要求 e _i按其范数从小到大排序。

该算法每轮最多将 n 个向量添加到 L₂。让 B 成为您预定义的上限，那么您将访问最多 n ^k -1 个向量，其中 k = 1+B/||e₁||。第一个约。n ^k'轮，列表大小为 n，其中 k' = B/||e _n ||。所以总的来说，你必须存储少于 N = n ^k' + (n ^k -1)/(n ^k'+1 ) 个列表。您可以在 O(n) 中生成一个新列表并将其添加到 O(log N) 中的 L₂ 中（二进制搜索正确的位置并将其链接插入其中）。

所以总体复杂度大概是 O(N⋅n⋅log N)，但请注意 N 是关于您要查找的向量的数量。

注意：很可能有更快的算法，但这是您可以尝试的。