Поиск всех соседних точек в многомерном пространстве

#алгоритм

На входе есть координаты точки, на выходе - нужно вывести координаты всех соседних
точек (прямых и по диагонали). Например для двух измерений и точки [0, 0] это будет
(для наглядности разбил на строки):

[[ 1,-1], [1, 0], [1, 1]

[ 0,-1], [0, 0], [0, 1]

[-1,-1], [-1,0], [-1,1]]


Проблема в том, что количество измерений может быть не 1 или 2, а до 6. Соответственно
хотелось бы узнать, какой алгоритм использовать в функции для вывода соседних точек
вместо 6 вложенных циклов?

Под соседними точками понимаются точки одна или несколько координат которых отличаются
на единицу (один "шаг") от точки на входе.
    

Ответы

Ответ 1

У Вас есть некоторая центральная точка с координатами X(x0, x1, ... xn) Тогда все
соседние точки будут иметь координаты Y(Y0, Y1, ... Yn), где Yk будет принимать каждое
значение из списка [хk - 1, хk, хk + 1]

Т.е. Все искомые точки мы можем представить как набор n-разрядных чисел в троичной
системе исчисления. Где минимальное число будет (x0 - 1, x1 - 1, ... xn - 1), а максимальное
(x0 + 1, x1 + 1, ... xn + 1)

Как происходит прибавление единицы к числу в n-ричной системе исчисления? Смотрят,
на значение младшего разряда. Если он меньше, чем n - 1, то просто прибавляют к нему
1. Если же равен, то сбрасывают его в 0, а 1 прибавляют к следующему разряду. Таким
образом, операция прибавления 1 оказывается рекурсивной.

Т.к. мы работаем только с n-разрядными числами, то если нам нужно будет сбросить
в 0 самый старший разряд, то считаем, что все числа закончились



function incPoint(APoint, ACenterPoint, ADim) {
  APoint[ADim]++;
  if (APoint[ADim] > ACenterPoint[ADim] + 1) {
    if (ADim == APoint.length - 1)
      return false;
    APoint[ADim] = ACenterPoint[ADim] - 1;
    return incPoint(APoint, ACenterPoint, ADim + 1);
  }
  return true;
}

var centerPoint = [0, 0, 0];
var curPoint = new Array(centerPoint.length);
for (var i = 0; i < curPoint.length; i++)
  curPoint[i] = centerPoint[i] - 1;
var idx = 1;
do {
  console.log(idx + ': ' +JSON.stringify(curPoint));
  idx++;
} while (incPoint(curPoint, centerPoint, 0))


Ответ 2

Вопрос можно переформулировать "нужны все возможные комбинации комбинации -1, 0 и
1 размерностью N".
Для этого можно воспользоваться функцией product() из библиотеки itertools в питоне. 

import itertools
N = 3
result = list(itertools.product([-1,0,1], repeat=N))