java - 计算列表的所有排列) inside List

Question

请求

由于此问题专门针对 Scala 编程语言，因此 Java 中的解决方案也可以。然而，需要注意的一件小事是在 Scala 解决方案中 tail recursion (Scaladocs) 绝对优于任何其他解决方案，而在 Java 中，非递归解决方案是有利的。这是因为它需要处理相当大的数据结构，以便可以相应地处理“最好是惰性流或类似流”中包含的每个项目，而不会收到 StackOverflowError。 (Javadocs)(多么讽刺)。

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

单个列表的排列问题

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

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

尾递归，惰性评估解决方案:

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