kotlin - 如何以一种功能风格生成一定长度的非穷举排列

Question

我正在尝试创建一个函数，该函数生成长度为n的所有可能排列，其中列出的对象是从集合S中非穷举地获取的。我正在尝试以Kotlin的功能风格实现此目的。

这是与此处的Python相同的问题:Generating permutations of a given length - Python
提供的答案是特定于Python的，因此对我没有帮助。

我也发现了这一点:
https://discuss.kotlinlang.org/t/cartesian-products/343
但是很难理解这是否是我要尝试做的事情。

我已经编写了一个接近完成任务的函数，但是它返回长度<= n的所有非穷举排列，这不是我想要的。这是代码:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>>{

    return if (components.isEmpty() || length <= 0 ){
        listOf(listOf())
    }else{
        components.map { x ->  nonexhaustivePermutations(length-1, components)
            .map { y -> listOf(x) + y } }
            .fold(listOf(listOf()), { x, y -> x + y} )
    }
}

如果有人指出我的错误或提出解决问题的全新方法，我将不胜感激。

Answer 1

您可以这样操作:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(emptyList())
    else nonexhaustivePermutations(length - 1, components)
        .flatMap { sub -> components.map { sub + it } }

现在，我将说明如何解决您的解决方案。首先，我将其重新格式化:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else components.map { elm ->
        nonexhaustivePermutations(length - 1, components).map { sub -> listOf(elm) + sub }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

第一个问题是 elm -> nonexhaustivePermutations(length - 1, components)。在这里，您在每个递归步骤中为每个 nonexhaustivePermutations调用具有相同参数的 elm。所以我建议将 components.map与 nonexhaustivePermutations(length - 1, components).map交换:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> listOf(elm) + sub }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

但是，除了显着提高性能之外，这种交换还对返回的元素进行了重新排序。可以通过用 listOf(elm) + sub替换 sub + elm来部分修复:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> sub + elm }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

如果运行此方法，您将看到它以长度增加的顺序返回排列。因此，首先要添加简短的排列。更精确地说，它们是在创建列表时添加的。因此，要摆脱它们，必须将 fold(listOf(listOf()))替换为 fold(emptyList()):

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> sub + elm }
    }.fold(emptyList()) { result, elm -> result + elm }

此版本正常工作。但是最后一行唯一要做的是列表扁平化。通过将 map替换为 flatMap，可以将flatting与映射结合起来:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).flatMap { sub ->
        components.map { elm -> sub + elm } 
    }