Cartesian product, and there's no real solution in...

# random

[karelpeeters]

Cartesian product, and there's no real solution in Kotlin except for nested loops I think.

[Ruckus]

Is there a general algorithm for an N dimensional Cartesian product? I was hoping to avoid all the intermediate lists created by many 2D Cartesian products.

[karelpeeters]

I've been looking for a while but now I've got an idea, give me a couple of minutes.

[Ruckus]

Sweet, thanks

[alex]

You can check guava sources: https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/CartesianList.java

[karelpeeters]

fun <T> List<List<T>>.cartesian(): List<List<T>> {
    val resultSize = this.fold(1) { a, l -> a * l.size }
    return List(resultSize) { i ->
        var left = resultSize - i
        this.map { list ->
            val j = left % list.size
            left /= list.size
            list[j]
        }
    }
}

[karelpeeters]

Not that happy mutating things from within a map but oh well.

[karelpeeters]

Also this should probably be lazy, a sequence or something like that.

[Ruckus]

@alex Thanks, I'll definitely read through that.

[Ruckus]

@karelpeeters That works pretty well, though the order is all wrong, but that shouldn't be too hard to fix. Thanks!

[karelpeeters]

Ah I thought resultSize - i fixed it but I didn't actually check simple smile

[karelpeeters]

Looks like Guava does the same thing: (index / axesSizeProduct[axis + 1]) % axes.get(axis).size()

[Ruckus]

It looks like that just moved the last iteration to the beginning, but left the rest in the same order.

[karelpeeters]

this.asReversed().map { ... }.asReversed() and just var left = i does fix it.

[karelpeeters]

But that's not great either.

[Ruckus]

Indeed