更快的排列生成器

Question

我已经为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
   }

- Ken Bloom

---

这个比基于数组的交换方法更快吗？还是你的意思是“最快的函数排列生成器”？（虽然你从未明确表示，但你添加了标签....） - Rex Kerr

我确实是指最快的函数排列生成器。因此，还没有尝试将其与基于数组交换的方法进行比较。 - Ken Bloom

有更好的算法。我不久前在Stack Overflow上看到了一个Scala算法，它返回下一个排列（假设一组索引），而不是所有排列的列表。它使用partition来查找下一个索引排列的点，并通常避免非尾递归调用。当然，Haskell的实现会运行得非常快，因为它不会预先计算任何东西。 :-) - Daniel C. Sobral

我应该指出，我对此的兴趣主要是为了引出优化技巧（如果有的话）。 - Ken Bloom

Answer 1

在Scala 2.9中，extempore添加了一些有用的方法到Scala集合类中，包括Seq.permutations方法，该方法可以生成该序列的所有排列。请参见链接文本。我还有一个非递归实现，我认为它的性能会更好。请参见SeqLike.permutations的非递归实现。

- Eastsun

---

嗯，目前Scala 2.9 svn中的版本似乎与我的实现类似，只是在尝试对10个项目列表进行排列时会耗尽内存，并且性能比我的差得多。你的版本对于短（5项）列表比我的慢，但对于较长（10项）列表更快。此外，你一次使用的内存较少，因为你返回一个迭代器。 - Ken Bloom

根据我的使用情况来看，尝试消除重复项可能会减慢速度，因为假定没有重复项，并且对于我的对象来说，使用==操作符需要很长时间（尽管我在这里讨论的基准测试是使用List[Int]执行的）。 - Ken Bloom

是的，Extempore或我的实现可用于具有重复项的Seq，例如List（1,1,1,2,2,2） - Eastsun