kotlin - 我如何让这个序列变得懒惰？

Question

我试图在 Kotlin 中生成列表的所有排列。有无数的例子返回 List<List<T>> ，但我的输入列表打破了这些，因为它们试图将所有结果都放入输出列表中。所以我想我会尝试制作一个返回 Sequence<List<T>> 的版本...

fun <T> List<T>.allPermutations(): Sequence<List<T>> {
    println("Permutations of $this")
    if (isEmpty()) return emptySequence()
    val list = this
    return indices
        .asSequence()
        .flatMap { i ->
            val elem = list[i]
            (list - elem).allPermutations().map { perm -> perm + elem }
        }
}

// Then try to print the first permutation
println((0..15).toList().allPermutations().first())

问题是，Kotlin 似乎只是放弃并要求提供其中一个嵌套序列的完整内容 - 因此它永远不会(或至少不会很长时间)最终到达第一个元素。 (它可能会在到达那里之前耗尽内存。)

我使用 Flow<T> 进行了相同的尝试, 结果相同。

据我所知，我的代码从来没有要求它将序列转换为列表，但似乎内部的某些东西无论如何都在对我做这件事，那么我该如何阻止呢？

Answer 1

如评论中所述，您错误地处理了空基本情况。您应该返回一系列一个空列表。

// an empty list has a single permutation - "itself"
if (isEmpty()) return sequenceOf(emptyList())

如果你返回一个空序列，first 将永远找不到任何东西——你的序列总是空的——所以它将继续计算序列直到它结束，并抛出异常。 (尝试使用较小的输入，例如 0..2!)