如何让Kotlin中生成全排列的Sequence实现惰性求值？

你的代码存在两个核心问题，导致调用first()时无法快速返回结果，甚至耗尽内存：

1. 错误的Base Case #

当前代码中，空列表返回emptySequence()，但排列的定义里，空列表的排列是包含空列表的单元素序列（即sequenceOf(emptyList())）。这个错误会导致所有非空列表的排列序列最终都是空的，程序为了找到第一个元素会无意义地遍历所有递归分支，陷入低效或资源耗尽的状态。

2. 低效的列表操作 #

每次递归中使用list - elem创建新列表，这是O(n)的操作，且会产生大量临时List对象，大幅增加内存占用和计算时间，尤其当输入列表较大时。

修复并优化后的实现 #

下面是修正了Base Case，且通过索引操作避免创建临时List的高效版本：

fun <T> List<T>.allPermutations(): Sequence<List<T>> {
    fun permute(remaining: List<T>, current: List<T>): Sequence<List<T>> = sequence {
        if (remaining.isEmpty()) {
            yield(current)
            return@sequence
        }
        for (i in remaining.indices) {
            val elem = remaining[i]
            val newRemaining = remaining.subList(0, i) + remaining.subList(i + 1, remaining.size)
            yieldAll(permute(newRemaining, current + elem))
        }
    }
    return permute(this, emptyList())
}

// 测试：快速获取第一个排列
println((0..15).toList().allPermutations().first())

优化点说明： #

• 修正Base Case：当剩余元素为空时，yield(current)输出当前构建完成的排列，确保递归能正确向上传递结果。
• 使用sequence构建器：通过yield和yieldAll实现真正的惰性，只有当需要获取下一个元素时才执行对应的递归分支。
• 减少临时列表开销：使用subList（视图，非拷贝）拼接新的剩余列表，比list - elem更高效。

如果想要第一个排列就是原列表本身，可以调整循环顺序，从最后一个元素开始遍历：

fun <T> List<T>.allPermutations(): Sequence<List<T>> {
    fun permute(remaining: List<T>, current: List<T>): Sequence<List<T>> = sequence {
        if (remaining.isEmpty()) {
            yield(current)
            return@sequence
        }
        // 从最后一个元素开始遍历，优先生成原顺序的排列
        for (i in remaining.indices.reversed()) {
            val elem = remaining[i]
            val newRemaining = remaining.subList(0, i) + remaining.subList(i + 1, remaining.size)
            yieldAll(permute(newRemaining, current + elem))
        }
    }
    return permute(this, emptyList())
}

这样调用first()会直接返回原列表[0,1,2,...,15]，无需递归到最底层，速度更快。

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