Упорядоченное перечисление точек решетки

Question

Настройка: Пусть ei - ортогональный базис для n-мерного евклидова пространства, но предположим, что ei имеет иррациональную (L1) норму. Пусть L будет множеством точек, полученных путем взятия линейных комбинаций ei с коэффициентами в натуральных числах (включая ноль). Теперь упорядочите точки в L сначала по их L1-норме, а затем лексикографически.

Вопрос: существует ли эффективный алгоритм для создания точек в L в порядке возрастания до некоторой предопределенной границы? Обратите внимание, что я не хочу производить точки и затем сортировать их, скорее я хочу пройтись по решетке по порядку.

Наблюдение: это легко сделать, если ei являются ортонормированными. Например, эта проблема решена здесь. В принципе, что-то подобное будет работать здесь, однако определить радиусы для итерации почти так же сложно, как решить проблему перечисления, поэтому это не очень полезно.

Answer 1

Как насчет этого:

Пусть L₁ и L₂ - списки векторов, где L₁ - список посещенных / обработанных векторов решетки, а L₂ - список списков векторов, которые будут посещены далее.

1. Установите L₁={ } и L₂ = {[0]}, где 0 - нулевой вектор.
2. Пусть v будет наименьшим вектором первого списка в L₂.
3. Посещение / обработка вектора v.
4. Добавьте список L = {v + e₁,..., v + e_n} в L₂, чтобы списки сортировались по наименьшему элементу. Генерируйте v + e_i, только если его норма меньше вашей предопределенной границы.
5. Вставьте v в конце L₁ и удалите его из передней части первого списка L₂.
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) и добавить его в L₂ в O(log N) (двоичный поиск в нужном месте и ссылка вставьте его туда).

Таким образом, общая сложность будет примерно равна O(N⋅n⋅log N), но обратите внимание, что N - это количество векторов, которые вы ищете.

Обратите внимание: скорее всего, есть более быстрый алгоритм, но это то, что вы можете попробовать.