在 Scala 中枚举排列的代码 [英] Code to enumerate permutations in Scala

问题描述

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

I coded a function to enumerate all permutations of a given list. What do you think of the code below?

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 <- permutations(tail); p1 <- interleave(head, p0)) yield p1
  }
}

推荐答案

给定一个 Seq，可以通过调用 permutations 方法已经有了排列.

Given a Seq, one can already have permutations by invoking the permutations method.

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

此外还有一种组合的方法:

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

关于您的实施，我想说三件事:

Regarding your implementation I would say three things:

(1) 好看

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

(2) Provide an iterator (which is the std collections approach that allows to discard elements). Otherwise, you can get lists with 1000! elements which may not fit in memory.

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


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) 您应该删除重复的排列(如 Luigi 所观察到的)，因为:

(3) You should remove duplicated permutations (as observed by Luigi), since :

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

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

这篇关于在 Scala 中枚举排列的代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！