algorithm - 通过子集的 flatMap 进行 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") 使用 pair - head, tail 进行递归调用:c - 无b - ca-bc

并排列前后部分。结果，我得到了后面三个的所有排列。接下来我的问题是:为什么递归调用不返回像“bc”、“cb”、“c”这样的中间语句，而是返回三个后面的有效集合。

Answer 1

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

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

要解决此问题，您可以将 perm without x 添加到每个循环的结果中，但您必须添加 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
  }
}