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

5

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

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

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

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

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

Это точки фиксированной нормы L1 в N-мерной кубической решетке:oeis.org/A035607 - некоторые формулы могут дать представление о том, как перечислить (для радиуса = 3,4 см.oeis.org/A035597 oeis.org/A035598) ninjagecko
@SteveJessop: Я думаю, тогда я был неправ, и что я действительно имел в виду, это расстояние до Манхэттена! izhak
@SteveJessop: я бы сказал, что это неограниченная сетка с источником где-то в ней, поэтому каждая координата может принимать любое положительное целое значение или ноль. (xi принадлежит {0, 1, 2, ...}) izhak
Набор значений, которые может принимать каждая координата:{0, 1}, право? Steve Jessop
в этом случае ответ «бесконечно много». Множество точек на расстоянии 1 Хэмминга от данной точки - это каждая точка, которая отличается ровно на 1 координату, что означает, что это полный набор из N осей, проведенных через точкуX, Единственной хорошей новостью является то, что она исчисляется бесконечно, поэтому вы можете перечислять их, если у вас есть неограниченное время ;-) Steve Jessop

Ваш Ответ

3   ответа
4

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

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

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

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

update: errh, подождите минуту, вы хотите использовать расстояние Манхэттена. Вызовпоперечный многогранник & Quot; сфера & Quot; может быть, но я нашел это довольно запутанным! В любом случае вы можете использовать тот же подход.

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

for (i = 0; i <= n; i++)
  for (j = 0; j + i <= n; j++)
    ...
       for (l = 0; l + ...+ j + i <= n; l++) {
         m = n - l - ... - j - i;
         printf(pat, i, j, ..., l, m);
       }

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

update

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

#!/usr/bin/perl

use strict;
use warnings;

sub enumerate {
    my ($d, $r) = @_;

    if ($d == 1) {
        return ($r ? ([-$r], [$r]) : [0])
    }
    else {
        my @r;
        for my $i (0..$r) {
            for my $s (enumerate($d - 1, $r - $i)) {
                for my $j ($i ? (-$i, $i) : 0) {
                    push @r, [@$s, $j]
                }
            }
        }
        return @r;
    }
}

@ARGV == 2 or die "Usage:\n  $0 dimension radius\n\n";
my ($d, $r) = @ARGV;
my @r = enumerate($d, $r);
print "[", join(',', @$_), "]\n" for @r;
Кажется, это работает правильно при тестировании сoeis.org/A035598 хотя не-Perl псевдокод будет хорошо.
Я считаю, что количество шагов в этом алгоритме масштабируется с гиперповерхностью, в отличие от гиперволота?
1

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

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

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

def lapp(lst, el):
    lst2 = list(lst)
    lst2.append(el)
    return lst2

def hypersphere(n, r, stem = [ ]):
    mystem  = lapp(stem, 0)
    if 1 == n:
            ret = [ mystem ]
            for d in range(1, r+1):
                    ret.append(lapp(stem,  d))
                    ret.append(lapp(stem, -d))
    else:
            ret     = hypersphere(n-1, r, mystem)
            for d in range(1, r+1):
                    mystem[-1] = d
                    ret.extend(hypersphere(n-1, r-d, mystem))
                    mystem[-1] = -d
                    ret.extend(hypersphere(n-1, r-d, mystem))
    return ret

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

Вместо того чтобы делатьlapp(someList, element)можно просто сказатьsomeList + [element]
ЛЕГО? Также вы посещаете места в интерьере или только места на поверхности? То есть, алгоритм масштабируется с поверхностью или объемом?
К сожалению, он масштабируется с (гипер) объемом. Проблема lapp () и двойная рекурсия в гиперсферу (, r-d,) являются остатками некоторых тестов. Дальнейшая оптимизация будетfor d in range(1, r+1) { mystem[-1] = d; sp = hypersphere(n-1, r-d, mystem); ret.extend(sp); for plane in sp { dipl = list(plane); dipl[0] = -d; ret.append(dipl) } } (извините за гибрид C-Python - я новичок в этом, не знаю, как правильно сделать отступ в комментариях)
0

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

  • Generate all integer partitions of R with cardinality ≤ D
  • For each partition, permute it without repetition
  • For each permutation, twiddle all the signs

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

from itertools import *

# we have to write this function ourselves because python doesn't have it...
def partitions(n, maxSize):
    if n==0:
        yield []
    else:
        for p in partitions(n-1, maxSize):
            if len(p)<maxSize:
                yield [1] + p
            if p and (len(p)<2 or p[1]>p[0]):
                yield [ p[0]+1 ] + p[1:]

# MAIN CODE    
def points(R, D):
    for part in partitions(R,D):             # e.g. 4->[3,1]
        part = part + [0]*(D-len(part))      # e.g. [3,1]->[3,1,0]    (padding)
        for perm in set(permutations(part)): # e.g. [1,3,0], [1,0,3], ...
            for point in product(*[          # e.g. [1,3,0], [-1,3,0], [1,-3,0], [-...
                  ([-x,x] if x!=0 else [0]) for x in perm
                ]):
                yield point

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

>>> result = list( points(4,3) )

>>> result
[(-1, -2, -1), (-1, -2, 1), (-1, 2, -1), (-1, 2, 1), (1, -2, -1), (1, -2, 1), (1, 2, -1), (1, 2, 1), (-2, -1, -1), (-2, -1, 1), (-2, 1, -1), (-2, 1, 1), (2, -1, -1), (2, -1, 1), (2, 1, -1), (2, 1, 1), (-1, -1, -2), (-1, -1, 2), (-1, 1, -2), (-1, 1, 2), (1, -1, -2), (1, -1, 2), (1, 1, -2), (1, 1, 2), (0, -2, -2), (0, -2, 2), (0, 2, -2), (0, 2, 2), (-2, 0, -2), (-2, 0, 2), (2, 0, -2), (2, 0, 2), (-2, -2, 0), (-2, 2, 0), (2, -2, 0), (2, 2, 0), (-1, 0, -3), (-1, 0, 3), (1, 0, -3), (1, 0, 3), (-3, -1, 0), (-3, 1, 0), (3, -1, 0), (3, 1, 0), (0, -1, -3), (0, -1, 3), (0, 1, -3), (0, 1, 3), (-1, -3, 0), (-1, 3, 0), (1, -3, 0), (1, 3, 0), (-3, 0, -1), (-3, 0, 1), (3, 0, -1), (3, 0, 1), (0, -3, -1), (0, -3, 1), (0, 3, -1), (0, 3, 1), (0, -4, 0), (0, 4, 0), (0, 0, -4), (0, 0, 4), (-4, 0, 0), (4, 0, 0)]

>>> len(result)
66

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

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

Похожие вопросы