在Scala中枚举排列的代码

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

导读：我编写了一个函数来枚举给定列表的所有排列。你觉得下面的代码怎么样？ def interleave(x:Int,l:List[Int]):List[List[Int]] = { l match { case Nil = List(List(x)) case (head::tail) = (x :: head :: tail) :: interleave(x,tail).map(head :: _) }}def

我编写了一个函数来枚举给定列表的所有排列。你觉得下面的代码怎么样？

def interleave(x:Int,l:List[Int]):List[List[Int]] = {
  l match { 
    case Nil => List(List(x))
    case (head::tail) =>
      (x :: head :: tail) :: interleave(x,tail).map(head :: _)
  }
}

def permutations(l:List[Int]):List[List[Int]] = {
  l match {
    case Nil => List(List())
    case (head::tail) =>
      for(p0 &lt- permutations(tail); p1 &lt- interleave(head,p0)) yield p1
  }
}

解决方法

给定一个Seq，可以通过调用排列方法来进行排列。

scala> List(1,2,3).permutations.mkString("n")
res3: String = 
List(1,3)
List(1,3,2)
List(2,1,3)
List(2,1)
List(3,2)
List(3,1)

此外，还有一种组合方法：

scala> List(1,3).combinations(2).mkString("n")
res4: String = 
List(1,2)
List(1,3)

关于你的实现，我会说三件事：

(1)好看

(2)提供一个迭代器(它是允许放弃元素的std集合方法)。否则，您可以获得1000的列表！可能不适合内存的元素。

scala> val longList = List((1 to 1000):_*)
longList: List[Int] = List(1,...


scala> permutations(longList)
java.lang.OutOfMemoryError: Java heap space
    at scala.collection.immutable.List.$colon$colon(List.scala:67)
    at .interleave(<console>:11)
    at .interleave(<console>:11)
    at .interleave(<console>:11)

(3)你应该删除重复的排列(如路易吉所观察到的)，因为：

scala> permutations(List(1,3))
res4: List[List[Int]] = List(List(1,3),List(1,1),List(3,1))

scala> List(1,3).permutations.toList
res5: List[List[Int]] = List(List(1,1))

（编辑：李大同）

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