创建 n 元笛卡尔积的惯用方法（几组参数的组合）

Question

要创建两组参数的所有可能组合并对其执行操作，您可以执行以下操作：

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

但是，如果您有（可能很多）更多参数，这很快就会变成 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 */
            }
        }
    }
}

你可以用 for 循环类似地写这个，或者像这样写：

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)

但我认为这样也好不到哪里去，因为这里存在一些可读性问题：d、c、b、a的动作写反了。无法推断出它们的类型规范，因此必须指定它们。与厄运金字塔相比，它是顺序颠倒的。提供可能值的集合的顺序无关紧要，但确实如此：您只想从一组集合中创建任意组合，但是，在此代码中，每一行都取决于前一行。

如果能有一种惯用的方式来做类似 Python's or Haskell's comprehensions, in which you (almost like the mathematical notation) 的事情，那就太好了：

{ /* 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!")
}

非常易于阅读：没有过多的缩进，您感兴趣的操作在前，数据源定义非常明确等。

旁注：flatMap-flatMap-...-flatMap-map.

也会出现类似的问题

关于如何在 Kotlin 中巧妙地创建 n 元笛卡尔积有什么想法吗？

Answer 1

我建议在 List 上使用 Arrow-kt's Applicative。看例子：

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") }

产生笛卡尔积

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 2

我自己创建了一个解决方案，所以我不必按照的建议添加依赖项。

我创建了一个接受两组或更多组任意大小的函数：

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()

示例：

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)

输出：

[[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]]

函数cartesianProductreturns一组列表。这些列表存在许多问题：

任何类型信息都将丢失，因为返回的集合包含包含输入集类型并集的列表。这些列表元素的返回类型是 Any?。函数returns一Set<List<*>>，即Set<List<Any?>>.
根据定义，列表的大小是未知的；它们不像 Kotlin Pair 或 Triple，其中大小根据定义是常量。然而，这些 lists/tuples 的大小应该等于输入集的数量，即上面示例中的 4。

但是，使用反射，我们可以解决这些问题。我们想要对每个列表采取的操作可以写成一个函数（例如，一些 class 的构造函数，它也只是一个函数）：

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"))

输出：

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

转换的签名（示例中的::Parameters）指定了列表内容的契约。

因为 map { ::Parameters.call(*it.toTypedArray()) } 不是很好，我创建了第二个扩展函数来为我完成它：

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

这样，代码就变得非常地道了：

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

代码可从 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 获得。我既不是说这是一个最佳解决方案，也不是说它在数学上是合理的（不是每个数学属性都明确地实现和测试），但它适用于问题的目的。

Answer 3

这是使用任意组合函数的另一种方法：

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 4

懒惰地生成一系列结果的解决方案。它采用列表而不是集合。

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())
    }
}

该算法的所有学分归于 Per L and his answer here. 通过使用 char 生成 5x5 二维数组进行测试，在我的 2 核机器上需要大约 4.4 秒来生成 33554432 个产品。

Answer 5

这是对@Erik 的回答的改编，它保持类型安全并且可以在功能链中使用：

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()

如果我们想要保持输入大小至少为 2 的要求，我将按照以下方式重写该解决方案以确保类型安全：

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()

Answer 6

我在 https://github.com/wellithy/pub/blob/master/src/main/kotlin/com/arxict/common/Cartesian.kt 创建了一个简单的实用程序，它支持 N-D 笛卡尔积和简单的 2-D。我选择了 Sequence 而不是 Collection 或 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 7

/**
 * 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 } }
}

由 https://gist.github.com/kiwiandroiddev/fef957a69f91fa64a46790977d98862b

提供

创建 n 元笛卡尔积的惯用方法（几组参数的组合）

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

idioms

set

cartesian-product

kotlin