Go语言无层级缓存全排列处理器实现及空间优化问询

问题背景 #

需求：编写Go语言函数，对输入的所有排列执行指定handler，无需返回完整排列。现有FindAllPermutationApplyHandler函数可实现该功能，但需缓存前n-1层级（同时缓存最近2层），以避免缓存最终层级。

针对提出的三个问题，解答如下：

1. 是否可避免缓存最近2层，将空间复杂度降至O(1)、O(n)或O(n²)？ #

O(1)空间复杂度不可能实现——因为至少需要维护当前正在生成的排列本身，这部分的空间就是O(n)。但完全可以做到O(n)级别的空间复杂度，不需要缓存前n-1层或最近2层。比如用原地修改的算法，只保留当前排列和少量状态变量，就能生成所有排列并调用handler。

2. 因第i层依赖第i-1层，是否此目标无法实现？ #

这个结论不成立。虽然排列的生成依赖前一个状态，但可以通过原地修改+状态回溯（回溯法）或者迭代式状态转换来避免缓存多层。比如回溯法中，每一步交换元素生成当前排列片段，调用handler后再交换回来恢复状态，全程只需要维护当前排列数组，空间复杂度为O(n)（递归版的话加上递归栈空间，也是O(n)）；迭代式算法则可以完全去掉递归栈，只用数组存储状态。依赖前一层不代表必须缓存历史层级，只要能在原地更新并回溯/转换状态，就能控制空间开销。

3. 若无法实现，是否有迭代式算法可降低空间复杂度？ #

当然有，**Heap's Algorithm（堆算法）**就是典型的迭代式全排列生成算法，空间复杂度为O(n)，完全不需要缓存多层状态。它通过交换数组内的元素生成下一个排列，每生成一个完整排列就可以直接调用handler，全程只需要维护当前排列数组和一个状态计数数组。

以下是Go语言实现的Heap's Algorithm示例：

package main

import "fmt"

// HeapPermute 用Heap算法生成全排列，每生成一个就调用handler
func HeapPermute(arr []int, handler func([]int)) {
	n := len(arr)
	// 状态计数数组，记录每个位置的交换次数
	count := make([]int, n)
	// 先处理初始排列
	handler(arr)

	i := 0
	for i < n {
		if count[i] < i {
			// 根据i的奇偶性选择交换位置
			if i%2 == 0 {
				arr[0], arr[i] = arr[i], arr[0]
			} else {
				arr[count[i]], arr[i] = arr[i], arr[count[i]]
			}
			// 调用handler处理当前排列
			handler(arr)
			count[i]++
			i = 0
		} else {
			// 重置当前位置的计数，移动到下一个位置
			count[i] = 0
			i++
		}
	}
}

func main() {
	// 测试示例
	testArr := []int{1, 2, 3}
	HeapPermute(testArr, func(perm []int) {
		fmt.Println(perm)
	})
}

这个实现中，仅用了O(n)的空间存储排列数组和计数数组，没有额外缓存任何历史层级，完全满足需求。

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