我已经为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
}
partition
来查找下一个索引排列的点,并通常避免非尾递归调用。当然,Haskell的实现会运行得非常快,因为它不会预先计算任何东西。 :-) - Daniel C. Sobral