https://kotlinlang.org logo
#random
Title
# random
k

karelpeeters

10/30/2019, 9:57 PM
Cartesian product, and there's no real solution in Kotlin except for nested loops I think.
r

Ruckus

10/30/2019, 9:59 PM
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.
k

karelpeeters

10/30/2019, 10:04 PM
I've been looking for a while but now I've got an idea, give me a couple of minutes.
r

Ruckus

10/30/2019, 10:05 PM
Sweet, thanks
k

karelpeeters

10/30/2019, 10:09 PM
Copy code
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]
        }
    }
}
Not that happy mutating things from within a
map
but oh well.
Also this should probably be lazy, a sequence or something like that.
r

Ruckus

10/30/2019, 10:17 PM
@alex Thanks, I'll definitely read through that.
@karelpeeters That works pretty well, though the order is all wrong, but that shouldn't be too hard to fix. Thanks!
k

karelpeeters

10/30/2019, 10:18 PM
Ah I thought
resultSize - i
fixed it but I didn't actually check simple smile
Looks like Guava does the same thing:
(index / axesSizeProduct[axis + 1]) % axes.get(axis).size()
r

Ruckus

10/30/2019, 10:20 PM
It looks like that just moved the last iteration to the beginning, but left the rest in the same order.
k

karelpeeters

10/30/2019, 10:23 PM
this.asReversed().map { ... }.asReversed()
and just
var left = i
does fix it.
But that's not great either.
r

Ruckus

10/30/2019, 10:27 PM
Indeed
134 Views