arrays - 如何在多维数组中查找邻居？

Question

假设我们有一个 N 维数组 A，其维度 N 在运行时确定。

我想知道是否有任何方法可以找到某个元素 A[a₁][a₂]...[a< sub>N] 而不调用递归方法。

在二维情况下很容易写出 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 循环。然而，在更高维数组上执行相同的任务似乎确实需要更多繁琐的工作。

Answer 1

您只需要遍历 Cartesian power集合 {-1, 0, 1} 到 N 以形成相对于当前索引的索引，注意丢弃全零组合(对应于当前元素):

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 实现。