list - 更快的置换生成器

Question

我为 Scala 列表编写了一个排列生成器，它生成给定列表的所有排列。到目前为止，我有以下基于 this Haskell implementation (而且我认为它比我尝试过的其他几个选项更有效)。有什么方法可以使这更有效，或者我是否涵盖了所有基础？

   /** For each element x in List xss, returns (x, xss - x) */
   def selections[A](xss:List[A]):List[(A,List[A])] = xss match {
      case Nil => Nil
      case x :: xs =>
         (x, xs) :: (for( (y, ys) <- selections (xs) )
            yield (y, x :: ys))
   }

   /** Returns a list containing all permutations of the input list */
   def permute[A](xs:List[A]):List[List[A]] = xs match {
      case Nil => List(Nil)

      //special case lists of length 1 and 2 for better performance
      case t :: Nil => List(xs)
      case t :: u :: Nil => List(xs,List(u,t))

      case _ => 
         for ( (y,ys) <- selections(xs); ps <- permute(ys))
            yield y :: ps
   }

Answer 1

在 Scala 2.9 临时添加了一些有用的方法到 Scala 集合类，包括一个 Seq.permutations，它生成这个 seq 的所有排列。见 link text .而且我有一个非递归实现，我认为它会有更好的性能。见 A non-recursive implementation of SeqLike.permutations