Máy phát hoán vị nhanh hơn

Question

Tôi đã viết một bộ tạo hoán vị cho danh sách Scala tạo tất cả các hoán vị của một danh sách nhất định. Cho đến nay, tôi đã có những điều sau dựa trên this Haskell implementation (và tôi nghĩ rằng nó hiệu quả hơn so với một số tùy chọn khác mà tôi đã thử). Có cách nào để làm cho điều này thậm chí hiệu quả hơn, hoặc tôi đã bao trả tất cả các căn cứ của tôi?

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

Mở rộng Scala 2.9 đã thêm một số phương pháp hữu ích vào lớp thu thập dữ liệu, bao gồm một Seq.permutations tạo ra tất cả hoán vị của seq này. Xem link text. Và tôi có một triển khai không đệ quy mà tôi nghĩ rằng sẽ có hiệu suất tốt hơn. Xem A non-recursive implementation of SeqLike.permutations