Вопрос: Учитывая число n≥ 2, сколько различных пар точек на nn - мерном n x n x n x n x n x n ... x nрешетке, где координаты в диапазоне от 0до n - 1, это расстояние по меньшей мере n , на части? Пары {(2,1,3,1), (3,2,1,3)}и {(3,2,1,3), (2,1,3,1)}не считаются отличными друг от друга, так как они состоят из одинаковых двух точек в обратном порядке. Обратите внимание, что общее количество пар растет очень быстро. Общее количество пар идет 6, 351, 32 640, 4 881 250, 1 088 367 840и т.д.

Тестовые случаи:

2 -> 0 (all pairs are at most a distance of sqrt(2) < 2 apart)
3 -> 28 (They must either be (2,2,1) or a permutation apart, or (2,2,2) apart. Each corner
has three non-corner (2,2,1) points corresponding to it. And each corner is associated 
with a corner pair that is a (2,2,2). Thus. 3.5 * 8 = 28.
4 -> 4,888
5 -> 1,501,948
6 -> 486,039,360 (I would like someone to verify this if possible)

Ваш код должен работать для n <= 5, по крайней мере, в теории. Не жестко закодируйте это, это стандартная лазейка.

MATL , 12 байт

tt:Z^tZPR>~z

Попробуйте онлайн!

объяснение

tt   % Implicit input n. Duplicate twice
     % STACK: n, n, n
:    % Range [1 2 ... n]
     % STACK: n, n, [1 2 ... n]
Z^   % Cartesian power. Gives an n^n × n matrix C where each row is a Cartesian tuple
     % STACK: n, C
t    % Duplicate
     % STACK: n, C, C
ZP   % Euclidean distance. Gives an n^n × n^n matrix D of pairwise distances
     % STACK: n, D
R    % Upper triangular part: sets elements below the main diagonal to 0. Call that U
     % STACK: n, U
>~   % Less than or equal? Element-wise. Gives a true-false matrix B
     % STACK: n, B
z    % Number of nonzeros. Implicitly display
     % STACK: number of entries in B that equal true

Желе , 14 13 байтов

1 байт благодаря Денису.

ṗ⁸Œc_/€ÆḊ€<ċ0

Попробуйте онлайн!

Quick Maffs версия

ŒgL€!P:@L!$×P
²S<
ḶœċçÐḟ²ð>0S’2*×⁸ạ⁹$Ѥð€S

Попробуйте онлайн!

Python 2 , 137 133 байта

lambda n:sum(n*n<=sum((o[i]-p[i])**2for i in range(n))for o,p in q(q(range(n),repeat=n),repeat=2))/2
from itertools import*
q=product

Мистер Xcoder & ovs: -4 байта. Попробуйте онлайн!

J , 40 байт

2%~[:+/^:_]<:[:+/&.:*:"1[:-"1/~#~#:i.@^~

Попробуйте онлайн!

Тайм-аут на TIO на 5, если вы используете расширенную точность ( 5xвместо 5). Я не собираюсь пытаться использовать 6 на моем компьютере, так как это, несомненно, приведет к сбою переводчика.

Нужны советы по игре в гольф, в частности, часть прошлого поколения координат. Я чувствую, что должен быть способ снять некоторые крышки.

]<:[:+/&.:*:"1может быть эквивалентно заменен на *:<:[:+/"1[:*:.

объяснение

Это объяснение сделано в REPL (три пробела указывают на команду, пробелы не указывают на вывод). Я буду готовиться к ответу.

Генерация координат

#~ #: i.@^~ дает все координаты, которые нам нужны на решетке.

^~является числом, возведенным в себя, и i.дает диапазон [0, n), где n - его ввод. @сочиняет эти функции.

   i.@^~ 2
0 1 2 3

#~ копирует номер самостоятельно, например

   #~ 3
3 3 3

#:преобразует свой правый аргумент в базу, указанную в массиве, указанном в качестве его левого аргумента. Количество цифр в массиве соответствует количеству цифр в этом базовом выводе (и вы можете иметь смешанную базу). Например,

   3 3 3 #: 0
0 0 0
   5 5 #: 120
4 0
NB. If you want 120 base 5 use #.inv
   #.inv 120
4 4 0

Таким образом, все вместе, это говорит, перечислите через все значения базы n (где n - вход) до n ^ n, эффективно давая нам наши координаты.

   (#~ #: i.@^~) 2
0 0
0 1
1 0
1 1

Получение расстояния между каждой парой

Сначала мы берем разницу каждой координаты со всеми остальными, используя /dyad -table и ~-reflexive. Обратите внимание, что это не учитывает тот факт, что порядок не имеет значения для пар: это создает повторяющиеся расстояния.

  NB. 2 {. takes the first two elements (I'm omitting the rest).
  2 {. -"1/~ (#~ #: i.@^~) 2
 0  0
 0 _1
_1  0
_1 _1

 0  1
 0  0
_1  1
_1  0

Затем мы используем этот глагол +/&.:*:в каждой координате (at "1, aka rank one). Этот глагол есть sum ( +/) под ( &.:) square ( *:). Under применяет правый глагол (квадрат), затем собирает его результаты и передает его в качестве аргумента левому глаголу (sum). Затем он применяет инверсию правого глагола (который будет квадратный корень).

   +/&.:*: 3 4
5
   +/&.:*:"1 ([: -"1/~ #~ #: i.@^~) 2
      0       1       1 1.41421
      1       0 1.41421       1
      1 1.41421       0       1
1.41421       1       1       0

Неудивительно, что многие расстояния одинаковы.

Подсчет расстояний больше или равно входу

Последняя часть проверяет, больше или равно ли расстояние входному значению ]<:. Затем все результаты суммируются с помощью +/^:_(сумма до сходятся), считая количество истинных значений. Затем это значение делится на 2 ( 2%~здесь это ~означает, что нужно поменять местами порядок аргументов %). Причина, по которой мы можем разделить на 2, заключается в том, что для каждого истинного спаривания будет другой для перевернутого порядка, кроме пар, которые являются координатой с самим собой. Это нормально, так как это приведет к расстоянию 0.