Как эффективно перечислить все точки сферы в n-мерной сетке
===========================================================

Скажем, у нас есть N-мерная сетка и некоторая точка X с координатами (x1, x2, ..., xN).
Для простоты можно предположить, что сетка не ограничена.

Пусть есть радиус R и сфера этого радиуса с центром в X, то есть множество всех точек в сетке, так что их манхэттенское расстояние от X равно R.

Я подозреваю, что их будет 2 * N * R таких точек.

Мой вопрос: как мне перечислить их эффективным и простым способом? "Перечислять" Я имею в виду алгоритм, который с учетом N, X и R будет создавать список точек, которые образуют эту сферу (где точка - это список ее координат).

ОБНОВЛЕНИЕ: Первоначально я назвал метрику, которую я использовал, «расстояние Хэмминга» по ошибке. Приношу свои извинения всем, кто ответил на вопрос. Спасибо Стиву Джессопу за то, что указал на это.

Рассмотрим минимальный выровненный по оси гиперкуб, ограничивающий гиперсферу, и напишите процедуру для перечисления точек сетки внутри гиперкуба.

Тогда вам нужна только простая функция фильтра, которая позволяет отбрасывать точки, которые находятся на кубе, но не в гиперсфере.

Это простое и эффективное решение для небольших размеров. Например, для 2D 20% точек, перечисленных для ограничивающего квадрата, отбрасываются; для 6D почти 90% точек гиперкуба отбрасываются.

Для более высоких измерений вам придется использовать более сложный подход: выполнить цикл по каждому измерению (вам может потребоваться использовать рекурсивную функцию, если число измерений является переменным). Для каждого цикла вам нужно будет отрегулировать минимальное и максимальное значения в зависимости от значений уже рассчитанных компонентов сетки. Что ж, попробуйте сделать это для 2D, перечислив точки окружности и, как только вы это поймете, обобщение процедуры на более высокие измерения будет довольно простым.

**update**: errh, подождите минуту, вы хотите использовать расстояние Манхэттена. Вызов[поперечный многогранник](https://en.wikipedia.org/wiki/Cross_polytope) & Quot; сфера & Quot; может быть, но я нашел это довольно запутанным! В любом случае вы можете использовать тот же подход.

Если вы хотите только перечислить точки на гиперповерхности перекрестного многогранника, решение также очень похоже, вы должны перебрать все измерения с соответствующими ограничениями. Например:

Для каждой точки, сгенерированной таким образом, вам нужно будет рассмотреть все варианты, возникающие в результате отрицания любого из компонентов, чтобы покрыть все грани, а затем сместить их на вектор X.

**update**

Реализация Perl для случая, когда X = 0:



Вы можете прокладывать свой путь рекурсивно из центра, считая нулевое расстояние один раз и работая над симметриями. Эта реализация Python работает с более низкоразмерным «стержнем» вектор и реализует один одномерный срез за один раз. Можно было бы сделать и обратное, но это подразумевало бы итерации по частичным гиперсферам. Хотя математически то же самое, эффективность обоих подходов сильно зависит от языка.

Если вы заранее знаете мощность целевого пространства, я бы рекомендовал написать итеративную реализацию.

Далее перечисляются точки в блоке гипер-LEGO с R = 16 в шести измерениях примерно за 200 мс на моем ноутбуке. Конечно, производительность быстро уменьшается с увеличением размеров или сфер.

(В этой реализации предполагается, что гиперсфера центрирована в начале координат. Было бы легче перевести все точки впоследствии, чем переносить координаты центра).



Вход: радиус R, размерность D

Generate all [integer partitions](https://en.wikipedia.org/wiki/Partition_%28number_theory%29) of R with cardinality ≤ D
For each partition, permute it without repetition
For each permutation, twiddle all the signs

Например, код на python:

Демо для радиуса = 4, размерность = 3:

(Выше я использовал`set(permutations(...))` получить перестановки без повторения, что неэффективно в целом, но это может не иметь значения здесь из-за природы точек. И если эффективность имеет значение, вы можете написать свою собственную рекурсивную функцию на выбранном вами языке.)

Этот метод эффективен, потому что он не масштабируется с гипервообъемом, а только масштабируется с гиперповерхностью, которую вы пытаетесь перечислить (может не иметь большого значения, за исключением очень больших радиусов: например, вы сэкономите примерно в 100 раз больше скорости если ваш радиус 100).