用于枚举Scala中的排列的代码

Question

我编写了一个函数来枚举给定列表的所有排列.您如何看待下面的代码？

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

Answer 1

给定Seq,可以通过调用permutations方法获得排列.

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:

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

关于你的实现,我会说三件事:

(1)它好看

(2)提供迭代器(这是允许丢弃元素的std集合方法).否则,您可以获得1000个列表!可能不适合记忆的元素.

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观察),因为:

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))

Answer 2

考虑一下这里的区别:你的版本

scala> permutations(List(1,1,2)) foreach println
List(1, 1, 2)
List(1, 1, 2)
List(1, 2, 1)
List(1, 2, 1)
List(2, 1, 1)
List(2, 1, 1)

参考版本:

scala> List(1,1,2).permutations foreach println
List(1, 1, 2)
List(1, 2, 1)
List(2, 1, 1)

Answer 3

我认为这样的函数已经存在于标准库中:Seq.permutations.那又为什么要重新发明轮子呢？

Answer 4

也许这个线程已经饱和了,但我想我会把我的解决方案放到混合中:

假设没有重复元素:

def permList(l: List[Int]): List[List[Int]] = l match {
   case List(ele) => List(List(ele))
   case list =>
     for {
       i <- List.range(0, list.length)
       p <- permList(list.slice(0, i) ++ list.slice(i + 1, list.length))
     } yield list(i) :: p
}

使用重复元素,防止重复(不漂亮):

def permList(l: List[Int]): List[List[Int]] = l match {
  case List(ele) => List(List(ele))
  case list =>
    for {
      i <- List.range(0, list.length)
      val traversedList = list.slice(0, i)
      val nextEle = list(i)
      if !(traversedList contains nextEle)
      p <- permList(traversedList ++ list.slice(i + 1, list.length))
    } yield list(i) :: p
}

它可能不是最"list-y",因为它在列表中使用了切片和索引,但它相当简洁并且看起来略有不同.它的工作原理是挑选出列表中的每个元素并计算剩余内容的排列,然后将单个元素连接到每个排列.如果有一种更惯用的方式来做到这一点,我很乐意听到它.

Answer 5

这是基于span的版本。

def perms[T](xs: List[T]): List[List[T]] = xs match {
  case List(_) => List(xs)
  case _ => for ( x <- xs
                ; val (l, r) = xs span { x!= }
                ; ys <- perms(l ++ r.tail)
                ) yield x :: ys
}