如何在多維數組中找到鄰居？

假設我們有一個N維數組A，其維數N在運行時確定。如何在多維數組中找到鄰居？

不知是否有什麼辦法可以找到在所有相鄰元件A的某些元素A的[A ] [一個] ... [一個_Ñ]而不調用遞歸方法。

在2維情況下，它是很容易編寫的A[i][j] 8個相鄰元件： A[i-1][j-1], A[i-1][j], A[i-1][j+1], A[i][j-1], A[i][j+1], A[i+1][j-1], A[i+1][j], A[i+1][j+1]，或代碼用一個簡單的for循環。然而，高維陣列上的相同任務似乎需要更乏味的工作。

來源

2017-08-10 Runzhong Zhao

嘗試遞歸，然後與我們分享您的代碼有多遠 – cahen

您可以將每個維度從'index - 1'循環到'index + 1';但是，每次您必須檢查*至少*一個索引不是零。這有一個昂貴的'O（d * 3^d）'複雜度，其中'd'是尺寸的數量，相比之下只有'O（3^d）'用於檢索所有元素。 – meowgoesthedog

你只需要遍歷該集合的Cartesian power {-1，0，1}到Ñ，以形成相對於當前一個的索引，小心棄去全零組合（這將對應到當前元素）：

algorithm neighbors(N : positive integer, 
        index : N-tuple of integers) 
    neighbors_list := empty list 
    for relative_index in cartesian_power({-1, 0, 1}, N) do 
     if not (relative_index is all zeros then) 
      new_index := [index[i] + relative_index[i] for i in 1..N] 
      neighbors_list := append(neighbors_list, new_index) 
     end 
    loop 
    return neighbors_list

請注意，這可以在可能和必要時進行懶惰評估。笛卡爾功率以及在非遞歸的方式實施：

algorithm cartesian_power(s : set, N : positive integer) 
    result := list(empty list) 
    repeat N times 
     result_step= empty list 
     for res in result do 
      for elem in s do 
       new_res := append(res, s) 
       result_step := append(result_step, new_res) 
      loop 
     loop 
     result := result_step 
    loop 
    return result

你也可以偷懶評估這個算法，儘管這是一個比較複雜一點，因爲你將不得不產生在最後一次迭代產生的元素最外面的循環。

這些算法沒有考慮像索引邊界或其他約束這樣的事情，因此您可能需要根據情況添加其他邏輯，但核心思想是相同的。

下面是一個例子實現作爲一個Python發電機：

from itertools import product 

def neighbors(index): 
    N = len(index) 
    for relative_index in product((-1, 0, 1), repeat=N): 
     if not all(i == 0 for i in relative_index): 
      yield tuple(i + i_rel for i, i_rel in zip(index, relative_index)) 

print(list(neighbors((1, 2))) 
>>> [(0, 1), (0, 2), (0, 3), (1, 1), (1, 3), (2, 1), (2, 2), (2, 3)] 

print(list(neighbors((1, 2, 3))) 
>>> [(0, 1, 2), 
(0, 1, 3), 
(0, 1, 4), 
(0, 2, 2), 
(0, 2, 3), 
(0, 2, 4), 
(0, 3, 2), 
(0, 3, 3), 
(0, 3, 4), 
(1, 1, 2), 
(1, 1, 3), 
(1, 1, 4), 
(1, 2, 2), 
(1, 2, 4), 
(1, 3, 2), 
(1, 3, 3), 
(1, 3, 4), 
(2, 1, 2), 
(2, 1, 3), 
(2, 1, 4), 
(2, 2, 2), 
(2, 2, 3), 
(2, 2, 4), 
(2, 3, 2), 
(2, 3, 3), 
(2, 3, 4)]

顯然，我在這裏作弊是因爲我使用一個Python內建函數來計算笛卡爾動力。然而，如果你去the documentation of itertools.product你會看到我上面寫的算法的Python實現。

來源

2017-08-10 15:43:09 jdehesa

如何在多維數組中找到鄰居？

回答

相關問題