How do I make this Sequence lazy?

Question

I was trying to generate all permutations of a list in Kotlin. There are a zillion examples out there which return a List<List<T>>, but my input list breaks those as they try to fit all the results in the output list. So I thought I would try to make a version returning 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())

Problem is, Kotlin just seems to give up and asks for the complete contents of one of the nested sequences - so it never (or at least not for a very long time) ends up getting to the first element. (It will probably run out of memory before it gets there.)

I tried the same using Flow<T>, with the same outcome.

As far as I can tell, at no point does my code ask it to convert the sequence into a list, but it seems like something internal is doing it to me anyway, so how do I stop that?

Answer 1

As mentioned in the comments, you have handled the empty base case incorrectly. You should return a sequence of one empty list.

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

If you return an empty sequence, first will never find anything - your sequence is always empty - so it will keep evaluating the sequence until it ends, and throw an exception. (Try this with a smaller input like 0..2!)