如何高效地枚舉n維網格中的所有球體點

Question

假設我們有一個N維網格和一些點X，其座標爲（x1，x2，...，xN）。 爲了簡單起見，我們可以假設網格是無界的。

要有一個半徑R和該半徑與X中心的球體，即集柵格的所有點，使得從X他們的曼哈頓距離等於R.

我懷疑他們的將是2 * N * R這樣的點。

我的問題是：我如何以高效和簡單的方式列舉它們？通過「列舉」我的意思是算法，給定N，X和R將產生形成這個球體的點列表（其中點是它的座標列表）。

更新：最初我錯誤地稱爲「海明距離」的度量。我向所有回答問題的人道歉。感謝Steve Jessop指出了這一點。

Answer 1

考慮限制超球面的最小軸對齊超立方體，並編寫枚舉超立方體內網格點的過程。

然後，您只需要一個簡單的過濾器功能，允許您放棄多維數據集上的點而不是超球面上的點。

這是一個簡單而高效的小尺寸解決方案。例如，對於2D，爲邊界正方形枚舉的點的20％被丟棄;對於6D，幾乎90％的超立方體點被丟棄。對於更高維度，您將不得不使用更復雜的方法：遍歷每個維度（如果維度數量可變，您可能需要使用遞歸函數）。對於每個循環，您必須根據已經計算的網格組件的值調整最小值和最大值。那麼，試着去做二維，列舉一個圓的點，一旦你理解它，將過程推廣到更高維將是非常簡單的。

更新：errh，等一下，你想使用曼哈頓距離。調用cross polytope「球體」可能是正確的，但我發現它很混亂！無論如何，你可以使用相同的方法。

如果您只想枚舉交叉多面體的超曲面上的點，那麼解決方案也非常相似，您必須在每個維度上使用適當的限制進行循環。例如：

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取代它們的產生

更新

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; 

Answer 2

可以活像按照遞歸的方式從中心開始，一次計算零距離並處理對稱性。這個Python實現工作在較低維度的「stem」向量上，並一次實現一個1維切片。人們也可以做相反的事情，但這意味着對部分超球體進行迭代。儘管數學上相同，但這兩種方法的效率都與語言密切相關。

如果您事先知道目標空間的基數，我會建議您編寫一個迭代實現。

以下列舉了筆記本計算機上大約200毫秒內六個維度上的R = 16超級樂高積木上的點數。當然，隨着更多維度或更大的球體，性能會迅速下降。

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 

（此實現假定超球在原點爲中心，這將是更容易的所有點後平移比沿中心的座標攜帶）。

Answer 3

輸入：半徑R，尺寸d

• 生成具有基數≤d
• 對於每個分區R的所有integer partitions，置換它沒有重複
• 對於每個排列，玩弄所有標誌

例如，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(...))得到不重複，這不是一般的高效率排列，但它可能這裏無關緊要因的性質點。如果效率很重要，你可以用自己選擇的語言編寫自己的遞歸函數。）

這種方法是有效的，因爲它不會隨着hypervolume擴展，而只是隨着超曲面擴展，這就是你想要的枚舉（除非是非常大的半徑，可能無關緊要：例如，如果您的半徑爲100，則會爲您節省大約100倍的速度）。