如何以函数式样式生成一定长度的非详尽排列

Question

我正在尝试创建一个函数来生成长度为 n 的所有可能排列，其中列出的对象是从集合 S 中非穷尽地获取的。我正在尝试使用 Kotlin 以函数式风格完成此操作。

这与 Python 此处提出的问题相同：Generating permutations of a given length - Python 提供的答案是 Python 具体的，因此对我没有帮助。

我还发现了这个： https://discuss.kotlinlang.org/t/cartesian-products/343 但是很难理解这是否是我正在尝试做的同一件事。

我已经编写了一个接近于完成任务的函数，但是它 returns 所有长度 <= 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>>{

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

Answer 2

你可以这样做：

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)。在这里，您在每个递归步骤中为每个 elm 使用相同的参数调用 nonexhaustivePermutations。所以我建议将 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 }

如果你运行这个方法，你会看到它returns按长度增加的顺序排列。所以首先添加短排列。更准确地说，它们是在创建列表时添加的。所以要摆脱它们，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:

，可以将扁平化与映射结合起来

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

如何以函数式样式生成一定长度的非详尽排列

How can one generate non-exhaustive permutations of a certain length in a functional style

functional-programming

combinatorics

kotlin