如何在多维数组中找到邻居？

假设我们有一个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

如何在多维数组中找到邻居？

回答

相关问题