Idiomatic way to create n-ary cartesian product (combinations of several sets of parameters)

Question

To create all possible combinations of two sets of parameters and perform an action on them, you can do:

setOf(foo, bar, baz).forEach { a ->
    setOf(0, 1).forEach { b ->
        /* use a and b */
    }
}

However, if you have (potentially many) more parameters, this quickly turns into a pyramid of doom:

setOf(foo, bar, baz).forEach { a ->
    setOf(0, 1).forEach { b ->
        setOf(true, false, null).forEach { c ->
            setOf("Hello,", "World!").forEach { d ->
                /* use a, b, c and d */
            }
        }
    }
}

You could write this similarly with for loops, or differently like so:

val dAction = { d: String -> /* use a, b, c and d */ }
val cAction = { c: Boolean? -> setOf("Hello,", "World!").forEach(dAction) }
val bAction = { b: Int -> setOf(true, false, null).forEach(cAction) }
val aAction = { a: Any? -> setOf(0, 1).forEach(bAction) }
setOf(foo, bar, baz).forEach(aAction)

But I don't think that's any better, because there are some readability issues here: d, c, b and a's actions are written in reverse. Their type specifications cannot be inferred, so they must be specified. It's reversed sequentially compared to the pyramid of doom. The order of the sets providing the possible values should not matter, but it does: you just want to create any combinations from a bunch of sets, however, in this code every line depends on the previous.

It would be very nice to have an idiomatic way of doing something like Python's or Haskell's comprehensions, in which you (almost like the mathematical notation) can do something like:

{ /* use a, b, c and d */
    for a in setOf(foo, bar, baz),
    for b in setOf(0, 1),
    for c in setOf(true, false, null),
    for d in setOf("Hello,", "World!")
}

Which is very easy to read: there is no excessive indentation, the action you're interested in goes first, the data sources are very clearly defined, etc.

Side note: similar problems occur with flatMap-flatMap-...-flatMap-map.

Any ideas about how to neatly create n-ary cartesian products in Kotlin?

Answer 1

I've created a solution myself, so I don't have to add a dependency as suggested by Omar's answer.

I created a function that takes two or more sets of any size:

fun cartesianProduct(a: Set<*>, b: Set<*>, vararg sets: Set<*>): Set<List<*>> =
    (setOf(a, b).plus(sets))
        .fold(listOf(listOf<Any?>())) { acc, set ->
            acc.flatMap { list -> set.map { element -> list + element } }
        }
        .toSet()

Example:

val a = setOf(1, 2)
val b = setOf(3, 4)
val c = setOf(5)
val d = setOf(6, 7, 8)

val abcd: Set<List<*>> = cartesianProduct(a, b, c, d)

println(abcd)

Output:

[[1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8]]

The function cartesianProduct returns a set of lists. There's a number of problems with these lists:

• Any type information is lost, because the returned set contains lists that contain the union of types of the input sets. The returned type of these lists' elements is Any?. The function returns a Set<List<*>>, i.e. Set<List<Any?>>.
• By definition, the size of the lists isn't known; they are not like a Kotlin Pair or Triple, where the size is a constant by definition. However, the size of these lists/tuples should be equal to the number of input sets, i.e. 4 in the example above.

However, using reflection, we can solve these problems. The action we want to take with every list can be written as a function (e.g. a constructor of some class, which is also just a function):

data class Parameters(val number: Int, val maybe: Boolean?) {
    override fun toString() = "number = $number, maybe = $maybe"
}

val e: Set<Int> = setOf(1, 2)
val f: Set<Boolean?> = setOf(true, false, null)

val parametersList: List<Parameters> = cartesianProduct(e, f).map { ::Parameters.call(*it.toTypedArray()) }

println(parametersList.joinToString("\n"))

Output:

number = 1, maybe = true
number = 1, maybe = false
number = 1, maybe = null
number = 2, maybe = true
number = 2, maybe = false
number = 2, maybe = null

The signature of the transform (::Parameters in the example) specifies the contract for the lists' contents.

Because map { ::Parameters.call(*it.toTypedArray()) } is not very nice, I've created a second extension function that does it for me:

fun <T> Set<List<*>>.map(transform: KFunction<T>) = map { transform.call(*it.toTypedArray()) }

With that, the code becomes quite idiomatic:

val parametersList: List<Parameters> = cartesianProduct(e, f).map(::Parameters)

The code is available from this GitHub Gist, where I will update it if I ever improve it. There are also tests: the cartesian product that includes any empty set returns the empty set, as is mathematically expected. I'm neither saying that this is an optimal solution, nor that it is mathematically sound (not every mathematical property is explicitly implemented and tested), but it works for the question's purpose.

Answer 2

I would recommend using Arrow-kt's Applicative on List. See the example:

val ints = listOf(1, 2, 3, 4)
val strings = listOf("a", "b", "c")
val booleans = listOf(true, false)

val combined = ListK.applicative()
    .tupled(ints.k(), strings.k(), booleans.k())
    .fix()

// or use the shortcut `arrow.instances.list.applicative.tupled`
// val combined = tupled(ints, strings, booleans)

combined.forEach { (a, b, c) -> println("a=$a, b=$b, c=$c") }

Which produces the Cartesian product

a=1, b=a, c=true

a=1, b=b, c=true

a=1, b=c, c=true

a=2, b=a, c=true

a=2, b=b, c=true

a=2, b=c, c=true

a=3, b=a, c=true

a=3, b=b, c=true

a=3, b=c, c=true

a=4, b=a, c=true

a=4, b=b, c=true

a=4, b=c, c=true

a=1, b=a, c=false

a=1, b=b, c=false

a=1, b=c, c=false

a=2, b=a, c=false

a=2, b=b, c=false

a=2, b=c, c=false

a=3, b=a, c=false

a=3, b=b, c=false

a=3, b=c, c=false

a=4, b=a, c=false

a=4, b=b, c=false

a=4, b=c, c=false

Answer 3

Solution which lazily generates a sequence of results. It takes lists though not sets.

fun <T> product(vararg iterables: List<T>): Sequence<List<T>> = sequence {

    require(iterables.map { it.size.toLong() }.reduce(Long::times) <= Int.MAX_VALUE) {
        "Cartesian product function can produce result whose size does not exceed Int.MAX_VALUE"
    }

    val numberOfIterables = iterables.size
    val lstLengths = ArrayList<Int>()
    val lstRemaining = ArrayList(listOf(1))

    iterables.reversed().forEach {
        lstLengths.add(0, it.size)
        lstRemaining.add(0, it.size * lstRemaining[0])
    }

    val nProducts = lstRemaining.removeAt(0)

    (0 until nProducts).forEach { product ->
        val result = ArrayList<T>()
        (0 until numberOfIterables).forEach { iterableIndex ->
            val elementIndex = product / lstRemaining[iterableIndex] % lstLengths[iterableIndex]
            result.add(iterables[iterableIndex][elementIndex])
        }
        yield(result.toList())
    }
}

All the credits for the algorithm go to Per L and his answer here. Tested with generating 5x5 2-d arrays with char, on my 2 core machine takes ~4.4 seconds to generate 33554432 products.

Answer 4

I've created a simple util at https://github.com/wellithy/pub/blob/master/src/main/kotlin/com/arxict/common/Cartesian.kt which supports N-D Cartesian product as well as a simple 2-D. I've chosen Sequence instead of Collection or Set.

typealias Family<T> = Sequence<T> // https://en.wikipedia.org/wiki/Indexed_family
typealias Tuple = Sequence<Any?> // https://en.wikipedia.org/wiki/Tuple
typealias CartesianProduct = Sequence<Tuple> // https://en.wikipedia.org/wiki/Cartesian_product

private val emptyTuple: Tuple = emptySequence()
private val zeroDCartesianProduct: CartesianProduct = sequenceOf(emptyTuple)

fun <T> Family<T>.toCartesianProduct(tuple: Tuple): CartesianProduct =
    map(tuple::plus)

fun <T> CartesianProduct.addFamily(family: Family<T>): CartesianProduct =
    flatMap(family::toCartesianProduct)

fun Sequence<Family<*>>.toCartesianProduct(): CartesianProduct =
    fold(zeroDCartesianProduct, CartesianProduct::addFamily)

fun <T, U> Family<T>.cartesianProduct(other: Family<U>): Sequence<Pair<T, U>> =
    flatMap { other.map(it::to) }

Answer 5

/**
 * E.g.
 * cartesianProduct(listOf(1, 2, 3), listOf(true, false)) returns
 *  [(1, true), (1, false), (2, true), (2, false), (3, true), (3, false)]
 */

fun <T, U> cartesianProduct(c1: Collection<T>, c2: Collection<U>): List<Pair<T, U>> {
  return c1.flatMap { lhsElem -> c2.map { rhsElem -> lhsElem to rhsElem } }
}

Courtesy of https://gist.github.com/kiwiandroiddev/fef957a69f91fa64a46790977d98862b

Answer 6

Here's another way to do it with an arbitrary combiner function:

fun <T, U, V> product(xs: Collection<T>, ys: Collection<U>, combiner: (T, U) -> V): Collection<V> =
    xs.flatMap { x ->
        ys.map { y ->
            combiner(x, y)
        }
    }

operator fun <T, U> Set<T>.times(ys: Set<U>): Set<Set<*>> =
    product(this, ys) { x, y ->
        if (x is Set<*>) x + y // keeps the result flat
        else setOf(x, y)
    }.toSet()

operator fun <T, U> List<T>.times(ys: List<U>): List<List<*>> =
    product(this, ys) { x, y ->
        if (x is List<*>) x + y // keeps the result flat
        else listOf(x, y)
    }.toList()

// then you can do

listOf(1, 2, 3) * listOf(true, false)

// or

setOf(1, 2, 3) * setOf(true, false)

// you can also use product's combiner to create arbitrary result objects, e.g. data classes

Answer 7

Here's an adaptation of @Erik's answer that maintains type safety and can be used in a functional chain:

fun <T> Collection<Iterable<T>>.getCartesianProduct(): Set<List<T>> =
    if (isEmpty()) emptySet()
    else drop(1).fold(first().map(::listOf)) { acc, iterable ->
        acc.flatMap { list -> iterable.map(list::plus) }
    }.toSet()

Here's how I'd rewrite that solution for type safety if we wanted to maintain the requirement for an input size of at least two:

fun <T> cartesianProduct(a: Set<T>, b: Set<T>, vararg sets: Set<T>): Set<List<T>> =
    (setOf(a, b).plus(sets))
        .fold(listOf(listOf<T>())) { acc, set ->
            acc.flatMap { list -> set.map { element -> list + element } }
        }
        .toSet()