枚举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("\n")
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)

此外，还有一种用于combinations的方法:

Furthermore there is also a method for combinations:

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

关于您的实现，我会说三件事:

Regarding your implementation I would say three things:

(1)好看

(2)提供一个迭代器(这是允许丢弃元素的std集合方法).否则，您可以获得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屋！