Generador de permutación más rápido

Question

He escrito un generador de permutación para las listas de Scala que genera todas las permutaciones de una lista dada. Hasta ahora, tengo lo siguiente basado en this Haskell implementation (y creo que es más eficiente que varias otras opciones que he probado). ¿Hay alguna forma de hacer esto aún más eficiente, o he cubierto todas mis 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 
    } 

Answer 1

En Scala 2,9 improvisada haber añadido algunos métodos útiles a clase de colección Scala, incluyen un Seq.permutations que la generación de todas las permutaciones de este ss. Ver link text. Y tengo una implementación no recursiva que creo que tendría un mejor rendimiento. Consulte A non-recursive implementation of SeqLike.permutations