通过子集的平面映射进行 Scala 排列

Question

我有进行排列的方法：

def permutations[T](lst: List[T]): List[List[T]] = lst match {
case Nil => List(Nil)
case x :: xs => permutations(xs) flatMap { perm =>
(0 to xs.length) map { num =>
(perm take num) ++ List(x) ++ (perm drop num)
}
}
}

首先，它需要一个递归调用，对 - 头，尾 对于 List("a"，"b"， "c")： c - 无 B - C A - 不列颠哥伦比亚

省并在零件之前和之后进行排列。结果，我有后面三个的所有排列。我的问题是接下来：为什么递归调用不返回像"bc"、"cb"、"c"这样的中间语句，而是从后面的三个返回有效集合。

Answer 1

好吧，在每次迭代中，您必须只返回与输入列表大小相同的列表，因为您返回形式(perm take num) ++ List(x) ++ (perm drop num)的排列，它将始终包含perm中的所有元素加上x元素。

因此，递归 - 如果每个循环仅返回与其输入大小相同的值(包括Nil的结束情况)，则最终结果必须仅包含相同大小的排列。

要解决此问题，您可以在不x的情况下添加perm到每个周期的结果中，但您必须添加distinct以消除重复：

def permutations[T](lst: List[T]): List[List[T]] = lst match {
case Nil => List(Nil)
case x :: xs => permutations(xs) flatMap { perm =>
((0 to xs.length) flatMap { num =>
List(perm, (perm take num) ++ List(x) ++ (perm drop num))
}).distinct
}
}