Блог

Я не математик, поэтому, пожалуйста, извините меня, если я использую неправильный словарь. Это не для какого-либо задания или домашней работы.

От точки (0,0) до (4, -1) существует пять возможных путей «такси-каб». Пусть n = сумма абсолютной разницы между точками, 5. Количество путей от одной до другой = (n * n-1) / 2 = 10. От одной точки до другой половина этого = 5.

Но когда я рисую это вручную, я насчитываю 13 «ребер» (правильный термин?) между всеми используемыми узлами или вершинами (?). Именно это число я хотел бы вычислить для любого n-мерного графика (вплоть до 6-ти измерений). Как получить 13 из вектора (4, -1)?

Если x-разность dx , а y-разность dy , то количество ребер равно

 NE = dx*(dy 1)   dy*(dx 1)
  

(количество горизонтальных ребер количество вертикальных ребер)

Для вашего случая dx=4, dy=1 , и NE =4*2 5*1=13
Для dx=4, dy=2 NE= 4*3 5*2=22

Та же логика работает для n-мерных сеток. Например, в 3D есть

 dy*(dx 1)*(dz 1) vertical edges (along OY)
dx*(dy 1)*(dz 1) horizontal edges (along OX)
dz*(dx 1)*(dy 1) edges in depth (along OZ)
  

это дает 144 ребра для куба 3x3x3

Простая программа на Python (подходит для любого языка) для вычисления этой величины для любого измерения:

 def numedges(dims:list):
    prod = 1
    for dim in dims:
        prod *= (dim   1)
    ne = 0
    for dim in dims:
        ne  = prod * dim // (dim 1)    #integer division
    return ne

print(numedges([2,4]))
print(numedges([3,3,3]))
print(numedges([2,3,4,5,6,7]))

>>>
22
144
96408
  

Используя reduce :

 from functools import reduce
def numedges(dims:list):
    product = reduce(lambda x,y: x*(y 1), dims, 1)
    return(reduce(lambda x,y: x product*y//(y 1), dims, 0))