list – 更快的排列生成器

发布时间：2020-12-16 09:28:49 所属栏目：安全来源：网络整理

导读：我为Scala列表编写了一个置换生成器,它生成给定列表的所有排列.到目前为止,我已经得到了基于 this Haskell implementation的以下内容(我认为它比我尝试过的其他几个选项更有效).有没有办法让这个更有效率,或者我覆盖了所有的基础？ /** For each element x i

我为Scala列表编写了一个置换生成器,它生成给定列表的所有排列.到目前为止,我已经得到了基于 this Haskell implementation的以下内容(我认为它比我尝试过的其他几个选项更有效).有没有办法让这个更有效率,或者我覆盖了所有的基础？

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

解决方法

在Scala 2.9中,extempore为scala集合类添加了一些有用的方法,包括一个Seq.permutations,它生成了这个seq的所有排列.请参阅 link text.我有一个非递归实现,我认为会有更好的性能.见 A non-recursive implementation of SeqLike.permutations

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!