Generatore di permutazione più veloce

Question

Ho scritto un generatore di permutazioni per liste Scala che genera tutte le permutazioni di una data lista. Finora, ho il seguente basato su this Haskell implementation (e penso che sia più efficiente di molte altre opzioni che ho provato). Ci sono dei modi per renderlo ancora più efficiente, o ho coperto tutte le mie basi?

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

In Scala 2.9 estemporanea hanno aggiunto alcuni metodi utili alla classe di raccolta scala, includono un Seq.permutations che genera tutte le permutazioni di questo ss. Vedi link text. E ho un'implementazione non ricorsiva che penso avrebbe una performance migliore. Vedere A non-recursive implementation of SeqLike.permutations