寻求N维网格搜索：无重复原点优先遍历的优雅生成算法

我实现了一个网格搜索模式序列生成器，但它仅靠记录并检查单元格坐标是否已输出来避免重复，性能表现很差。我认为应当存在一种优雅的迭代算法，可从原点出发，按与原点距离大致递增的顺序，无重复地遍历搜索网格中的每个单元格一次，且无需这种占用内存的机制。这种算法/序列应当有对应的名称，可应用于整数约束满足问题的局部搜索。

现有TypeScript实现代码 #

function *spiralWalk(dimensions : number) : Generator<number[]> {
    function *spiralWalk_(dimensions : number, digits : number) : Generator<number[]> {
        if (dimensions === 0) {
            yield [ ];
        } else {
            for (let digit = 0; digit < digits; digit++) {
                for (let subwalk of spiralWalk_(dimensions - 1, digits)) {
                    let sym = digit % 2 === 0 ? digit / 2 : -Math.floor(digit / 2)
                    yield [ sym, ...subwalk ];
                }
            }
        }
    }

    // 这个`seen_it_before`机制是性能瓶颈，需要移除
    let seen_it_before : { [key : string] : boolean } = {};

    for (let digits = 2; true; digits++) {
        for (let candidate of spiralWalk_(dimensions, digits)) {
            let key = candidate.toString();
            if (!seen_it_before[key]) {
                seen_it_before[key] = true;
                yield candidate;
            }
        }
    }
}

for (let x of spiralWalk(4).take(100)) {
    console.log(x);
}

代码逻辑说明 #

该实现的逻辑为：在N维空间中，先穷举Base-2的所有组合，再依次穷举Base-3、Base-4……的组合，每次提升基数时会出现大量重复组合，因此通过seen_it_before来过滤重复。其中let sym = digit % 2 === 0 ? digit / 2 : -Math.floor(digit / 2)语句将符号映射为以0为中心的偏移序列0, 1, -1, 2, -2, 3, -3, ...。

spiralWalk(2)生成的序列示例 #

[0, 0] 
[0, 1] 
[1, 0] 
[1, 1] 
[0, -1] 
[1, -1] 
[-1, 0] 
[-1, 1] 
[-1, -1] 
[0, 2] 
[1, 2] 
[-1, 2] 
[2, 0] 
[2, 1] 
[2, -1] 
[2, 2] 
[0, -2] 
[1, -2] 
[-1, -2] 
[2, -2] 
[-2, 0] 
[-2, 1] 
[-2, -1] 
[-2, 2] 
[-2, -2] 
[0, 3] 
[1, 3] 
[-1, 3] 

内容的提问来源于stack exchange，提问作者Jason Kleban