请求

由于此问题专用于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)

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

虽然很懒,但这并不能解决我的问题。我追求的是以下内容:
// List of lists
val lists = List(
        List(1, 2, 3),
        List(3, 2),
        List(4, 3, 2, 4))

计算内部List的所有可能排列,同时对外部List内的List保持相同的顺序,并在外部List内的每个List包含相同数量的元素。意思是,应该以各种可能的方式将内部List与其他内部List排列在一起,就好像它们已经被展平了一样,同时仍保持与以前相同的顺序和包含相同数量的元素。

因此,一种排列可能会产生:
List(List(1, 3, 2), List(3, 2), List(3, 4, 4, 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)

09-10 05:42
查看更多