Swift多线性映射可变维度索引的高效枚举算法问询

刚好之前处理过类似的场景，用迭代式的进制进位算法就能完美解决这个问题——既避开了嵌套循环（毕竟维度编译时未知），又比递归高效得多，完全没有递归栈的开销，效率和手动写嵌套循环几乎一致。

核心思路拆解 #

我们可以把每个索引数组看作一个「可变进制数」：

• 每个位置的“进制数”就是Shape对应维度的大小（比如Shape是[p,q,r]，最右侧的索引是最低位，进制为r；中间是q，最左侧是p）
• 从全起始值（0-based就是全0，1-based就是全1）开始，每次对最右侧的索引加1：
  1. 如果加1后没超过该维度的最大值，直接处理当前索引组合就行
  2. 如果超过了，就把这个索引重置为起始值，然后向左移动一位继续加1，直到找到一个可以递增的位置
  3. 当所有索引都溢出（连最左侧的索引都要进位），说明所有组合都遍历完了，可以停止

代码实现（Swift示例） #

假设我们用的是0-based索引（绝大多数编程语言的数组默认逻辑），下面是完整的遍历逻辑，直接加到你的MultilinearMap扩展里就行：

extension MultilinearMap {
    func iterateAllIndexes(_ handler: ([Int]) -> Void) {
        let dimensions = self.shape // 你的Shape数组，比如[p,q,r]
        guard !dimensions.isEmpty else { return }
        
        // 初始化索引数组：全0（0-based起始值）
        var currentIndexes = Array(repeating: 0, count: dimensions.count)
        
        while true {
            // 处理当前索引组合：可以调用elementAt，或者做任何你需要的操作
            handler(currentIndexes)
            
            // 从最右侧开始尝试递增+进位
            var currentDim = dimensions.count - 1
            var needCarry = true
            
            while needCarry && currentDim >= 0 {
                currentIndexes[currentDim] += 1
                if currentIndexes[currentDim] < dimensions[currentDim] {
                    // 当前维度没溢出，停止进位
                    needCarry = false
                } else {
                    // 溢出了，重置为0，继续向左进位
                    currentIndexes[currentDim] = 0
                    currentDim -= 1
                }
            }
            
            // 如果needCarry还是true，说明所有维度都溢出，遍历结束
            if needCarry {
                break
            }
        }
    }
}

1-based索引的适配

如果你的索引是1-based（比如你示例里的[1,3,2]），只需要改两处：

1. 初始化currentIndexes为全1
2. 溢出判断和重置值改成对应逻辑

修改后的关键代码片段：

// 初始化1-based索引数组
var currentIndexes = Array(repeating: 1, count: dimensions.count)

// ...

currentIndexes[currentDim] += 1
if currentIndexes[currentDim] <= dimensions[currentDim] {
    needCarry = false
} else {
    currentIndexes[currentDim] = 1
    currentDim -= 1
}

为什么这个方法这么好用？ #

• 时间效率拉满：O(N)复杂度，N是总元素数，每个索引组合只处理一次，没有冗余计算
• 空间占用极小：只需要存储当前的索引数组，空间复杂度是O(D)（D是维度数），完全没递归栈的负担
• 兼容性极强：不管维度是2维、5维还是10+维，逻辑都能稳定运行，完全不需要提前知道维度数

使用示例 #

你可以直接这样调用，遍历所有元素：

let myMap = MultilinearMap(shape: [2,3,4])
myMap.iterateAllIndexes { indexes in
    let element = myMap.elementAt(indexes: indexes)
    print("Index组合: \(indexes)，对应元素: \(element)")
}

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