计算 List 内 List(s) 的所有排列

Question

要求

由于此问题专门针对 Scala 编程语言，因此 Java 中的解决方案也可以。然而，需要注意的一件小事是，在 Scala 解决方案中 tail recursion (Scaladocs) is definitely favorable over any other, and in Java, a non-recursive solution is favorable. This is due to the fact that it needs work on quite large structures of data so that each item contained by the "preferably lazy Stream or similar" can be handled accordingly, without receiving a WhosebugError (Javadocs)（多么讽刺）。

应该置换的数据类型是 Scala List (Scaladoc)，但是使用 Java 数组和有点复杂的循环结构来响应解决方案是完全可以的。

单个列表的排列问题

在 Scala 中，以下是检索给定集合类型的所有排列的完全有效的方法。以下方法 returns 以惰性方式包含所有排列的迭代器：

val permutations = List(1, 2, 3, 4, 5, 6, 7).permutations.take(5)

如前所述，这将产生一个迭代器，其中包含该特定列表的排列。由于它是惰性的，我们只能从序列中取出五个。根据我的理解，这很好，只要我们不在迭代器上调用 toString，因为这将导致迭代器计算所有可用数据并将其作为字符串返回。

虽然偷懒，但这并不能解决我的问题。我所追求的是以下内容：

// List of lists
val lists = List(
        List(1, 2, 3), 
        List(3, 2), 
        List(4, 3, 2, 4))

计算内部列表的所有可能排列，同时保持外部列表中列表的相同顺序，外部列表中每个列表包含的元素数量相同。意思是，内部 List(s) 应该以所有可能的方式与其他内部 List(s) 一起排列，就好像它们已被展平一样，同时仍保持与以前相同的顺序并包含相同数量的元素。

一个排列可能因此产生：

List(List(1, 3, 2), List(3, 2), List(3, 4, 4, 2))

此外

看来我还不够聪明，无法靠自己征服这里列出的概念。任何指针，如果不是完整的代码，将不胜感激！如果您有任何问题，请发表评论，我会尽力澄清，无论是在评论中还是通过对现有问题进行小幅修改。

如果您对这个问题有答案，但使用的语言未在此问题中列出，尽管如此，请尽管尝试回答，但我主要追求的是此类排列的概念！

Answer 1

如果外部 List 的大小已知且恒定，则可以按如下方式完成。

val ls = List(List(1, 3, 2), List(7, 8), List(9, 4, 4, 5))

val allPerms: Iterator[List[List[Int]]] = for {
  a <- ls(0).permutations
  b <- ls(1).permutations
  c <- ls(2).permutations
} yield List(a,b,c)

在这个例子中，结果 Iterator 有 144 个元素，这是我们应该期望的：6 X 2 X 12 = 144

如果外部 List 长度是可变的，那么任务会有点复杂。

更新

在这种情况下 "more complicated" 意味着我必须考虑一段时间才能找到可能的解决方案。

def getAllPerms[A]( in: List[List[A]]
                  , acc: List[List[A]] = List()
                  ): Iterator[List[List[A]]] = in match {
  case end :: Nil => end.permutations.map(acc :+ _)
  case hd :: tl => hd.permutations.flatMap(x => getAllPerms(tl, acc :+ x))
  case Nil => Iterator()  // just to be complete
}

这是递归但不是尾递归。它确实通过了我有限的一组测试。试一试。

Answer 2

尾递归，惰性计算解决方案：

@tailrec
def tailRecCombineWith(permutatedLists: Iterator[List[List[Int]]], remainingLists: List[List[Int]]): Iterator[List[List[Int]]] = remainingLists match {
  case Nil => permutatedLists
  case head :: tail => tailRecCombineWith(for {
    a: List[List[Int]] <- permutatedLists
    b: List[Int] <- head.permutations
  } yield a :+ b, tail)
}

val result: Iterator[List[List[Int]]] = 
  tailRecCombineWith(lists.head.permutations.map(List(_)), lists.tail)

计算 List 内 List(s) 的所有排列

Calculate all permutations for List(s) inside List

java

scala

permutation

scala-collections

要求

单个列表的排列问题

此外