如何用Kotlin函数式风格生成指定长度的非穷尽排列？

首先，我们来分析你当前代码的问题所在：

你的代码的核心错误 #

1. Base Case 处理不当：
   你当前的代码在components.isEmpty() || length <=0时统一返回listOf(listOf())，这会导致递归过程中生成长度小于n的排列。比如当length=0时返回的空列表，会被上层递归组合成长度为1的排列，最终累积出从长度0到n的所有排列，而不是仅保留长度恰好为n的。

2. Fold初始值错误：
   你使用listOf(listOf())作为fold的初始值，这会把空列表（长度为0的"排列"）直接加入到结果中，进一步导致结果包含了不需要的短排列。

修正后的代码 #

我们只需要调整Base Case和Fold初始值，就能得到你想要的结果：

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> {
    return when {
        // 当长度为0时，返回仅包含空列表的列表（作为递归终止的基础）
        length == 0 -> listOf(emptyList())
        // 元素集合为空且长度>0，无法生成任何排列
        components.isEmpty() -> emptyList()
        else -> components.map { x ->
            nonexhaustivePermutations(length - 1, components)
                .map { y -> listOf(x) + y }
        }
        // 使用空列表作为fold初始值，避免混入空排列
        .fold(emptyList()) { acc, permutations -> acc + permutations }
    }
}

更简洁的函数式实现思路 #

其实，固定长度的非穷尽排列本质上是集合S的n次笛卡尔积（因为每个位置都可以重复选取集合中的元素，且顺序有意义）。我们可以基于这个思路实现更简洁的版本：

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> {
    require(length >= 0) { "Length must be a non-negative integer" }
    
    return when {
        length == 0 -> listOf(emptyList())
        components.isEmpty() -> emptyList()
        // 从长度1的排列开始，迭代n-1次，每次将现有排列与集合元素组合成长度+1的排列
        else -> (1 until length).fold(components.map { listOf(it) }) { acc, _ ->
            acc.flatMap { currentPerm -> components.map { currentPerm + it } }
        }
    }
}

这个实现的逻辑说明： #

• 当length=1时，直接返回集合中每个元素单独组成的列表；
• 对于length>1的情况，我们通过fold迭代n-1次：每次迭代都将现有的所有排列（长度为k）与集合中的每个元素组合，生成长度为k+1的新排列；
• 最终得到的就是所有长度恰好为n的非穷尽排列。

测试一下这个函数，比如输入length=2，components=listOf("a", "b")，会返回：
[[a, a], [a, b], [b, a], [b, b]]，完全符合你的需求。

内容的提问来源于stack exchange，提问作者Emil Jansson