创建 n 元笛卡尔积的惯用方法(多组参数的组合) [英] Idiomatic way to create n-ary cartesian product (combinations of several sets of parameters)

问题描述

要创建两组参数的所有可能组合并对它们执行操作，您可以:

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

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

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)

但我不认为这样更好，因为这里存在一些可读性问题:d、c、b 和 a 的动作是相反的.无法推断它们的类型规范，因此必须指定它们.与末日金字塔相比，它是顺序颠倒的.提供可能值的集合的顺序无关紧要，但确实如此:您只想从一堆集合中创建任何组合，但是，在此代码中，每一行都依赖于前一行.

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.

如果有一种惯用的方式来做类似 Python 的 或 Haskell 的 推导式，其中您(几乎像数学符号)可以做这样的事情:

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.

附注:flatMap-flatMap-...-flatMap-map 也会出现类似问题.

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

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

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

推荐答案

我自己创建了一个解决方案，所以我不必像 奥马尔的回答.

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

例子:

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

cartesianProduct 函数返回一组列表.这些列表存在许多问题:

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

• 任何类型信息都会丢失，因为返回的集合包含包含输入集合类型联合的列表.这些列表元素的返回类型是Any?.该函数返回一个Set，即Set.
• 根据定义，列表的大小是未知的；它们不像 Kotlin 的 Pair 或 Triple，其大小根据定义是一个常数.但是，这些列表/元组的大小应该等于输入集的数量，即上例中的 4 个.

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

输出:

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)指定列表内容的协定.

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

因为 map { ::Parameters.call(*it.toTypedArray()) } 不是很好，所以我创建了第二个扩展函数来为我做这件事:

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)

代码可从 此 GitHub Gist 获得，如果我有改进，我会在其中更新它.还有测试:包含任何空集的笛卡尔积返回空集，如数学预期的那样.我既不是说这是一个最佳解决方案，也不是说它在数学上是合理的(并非每个数学属性都被明确实现和测试)，但它适用于问题的目的.

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.

这篇关于创建 n 元笛卡尔积的惯用方法(多组参数的组合)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！