Cartesian product of possibly-infinite sequences

combine.kt

import org.junit.jupiter.api.Test

fun <T> combine(sequences: List<Sequence<T>>): Sequence<List<T>> = sequence {
    if (sequences.isEmpty()) return@sequence

    if (sequences.size == 1) {
        for (x in sequences[0]) {
            yield(listOf(x))
        }
        return@sequence
    }

    val iterators = sequences.map { it.iterator() }
    val current = iterators.map { it.next() }.toMutableList()
    val amount = MutableList(sequences.size) { 1 }
    var index = 0

    fun advance(index: Int): Boolean {
        if (iterators[index].hasNext()) {
            current[index] = iterators[index].next()
            amount[index]++
            // println("advanced index=$index to amount=${amount[index]}, current=${current[index]}")
            return true
        } else {
            return false
        }
    }

    yield(current)

    while (true) {
        index = (index - 1).mod(sequences.size)
        if (!advance(index)) break

        val sub: MutableList<Sequence<T>> = mutableListOf()
        for (i in sequences.indices) {
            if (i == index) continue
            sub += sequences[i].take(amount[i])
        }
        for (p in combine(sub)) {
            val q = p.toMutableList()
            q.add(index, current[index])
            // println("index=$index, p = $p, q = $q")
            yield(q)
        }
    }
}

class CombineTest {
    @Test
    fun `test combine`() {
        val xs = generateSequence(1) { it + 1 }
        val ys = generateSequence('A') { it + 1 }
        val zs = generateSequence(100) { it + 100 }
        for (c in combine(listOf(xs, ys, zs)).take(30)) {
            println(c)
        }
    }
}

output.txt

[1, A, 100]
[1, A, 200]
[1, B, 100]
[1, B, 200]
[2, A, 100]
[2, A, 200]
[2, B, 100]
[2, B, 200]
[1, A, 300]
[1, B, 300]
[2, A, 300]
[2, B, 300]
[1, C, 100]
[1, C, 200]
[2, C, 100]
[2, C, 200]
[1, C, 300]
[2, C, 300]
[3, A, 100]
[3, A, 200]
[3, B, 100]
[3, B, 200]
[3, A, 300]
[3, B, 300]
[3, C, 100]
[3, C, 200]
[3, C, 300]
[1, A, 400]
[1, B, 400]
[2, A, 400]