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

Question

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

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

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

Answer 1

Как об этом:

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

1. Установить L₁ = {} и L₂ = {[0]}, где 0 - нулевой вектор.
2. Пусть v - наименьший вектор первого списка в L₂.
3. Посещение/процесс вектор v.
4. Добавить в список L = {V + e₁, ..., V + е _п} к L₂, так что списки сортируются по наименьшему элементу. Создавайте только v + e _i, если его норма меньше вашей предопределенной границы.
5. Вставьте v в конец L₁ и снимите его с передней части первого списка L₂.
6. Если первый список пуст, удалите его из L₂. Если нет, переместите его в нужное место.
7. Если L₂ не пусто, Гото 2.

Этот алгоритм требует е _я быть отсортированный по их норме от мала до велика.

Этот алгоритм добавляет не более 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 - это количество векторов, которые вы ищете.

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