Faster permutation generator

I've written a permutation generator for Scala lists that generates all permutations of a given list. So far, I've got the following based on this Haskell implementation (and I think it's more efficient than several other options I've tried). Are there any ways to make this even more efficient, or have I covered all my bases?

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

---

In Scala 2.9 extempore have added some useful methods to scala collection class, include a Seq.permutations which generating all permutations of this seq. See link text. And I have a non-recursive implementation which I think would have a better performance. See A non-recursive implementation of SeqLike.permutations

链接地址: http://www.djcxy.com/p/4154.html

上一篇: 如何使用Projections和Criteria获得不同的结果

下一篇: 更快的置换生成器