更快的置换生成器
我为Scala列表编写了一个置换生成器，它生成给定列表的所有排列。 到目前为止，我已经得到了以下基于Haskell实现的以下内容（并且我认为它比我尝试过的其他几个选项更高效）。 有没有什么方法可以使这个效率更高，还是我覆盖了所有的基地？
/** 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
}
在Scala 2.9中，extempore为scala collection类增加了一些有用的方法，包括一个Seq.permutations，它产生了这个seq的所有排列。 请参阅链接文字。 我有一个非递归实现，我认为它会有更好的性能。 请参阅SeqLike.permutations的非递归实现
链接地址: http://www.djcxy.com/p/4153.html