斯卡拉 - 折叠多个Seqs

我该如何转换一个Seq [Seq [Int]，使得每个内部Seq包含其他两个列表中的元素？斯卡拉 - 折叠多个Seqs

//Example: 
val A = Seq(1, 2, 3) 
val B = Seq(4, 5) 
val C = Seq(6, 7, 8) 
val input(A,B,C) 
/** 
    * INPUT: [(1,2,3), (4,5), (6,7,8)] 
    * OUTPUT:[(1,4,6), (1,4,7), (1,4,8), (1,5,6), ..., (3,5,8)] 
    */ 
def process(input: Seq[Seq[Int]]): Seq[Seq[Int]] = { 
    //unknown 
}

来源

2016-08-24 J.D.

你为什么不分享我们的一些解决方案作为出发点？ – pedrofurla

查看此答案[here]（http://stackoverflow.com/a/8218167/4496364）。 –

如果最终以比您开始的更多的“Seq”对象，那么看起来好像没有任何东西正在崩溃。 – Eric

如果这是一个家庭作业，我建议你不要在下面转（你可能会进行逆向工程一个简单的解决方案，涉及递归出来的我猜的）。但是，如果你真的只是好奇这一点，有一些漂亮的技巧。

def convert[T](xs: Seq[Seq[T]]): Seq[Seq[T]] = 
    xs.foldLeft(Seq(Seq[T]()))((bs,ns) => for (b <- bs; n <- ns) yield b :+ n)

foldLeft强调的事实，你会从输入的左侧开始，在同一时间工作的方式正确的Seq。然后，对于每个Seq，你会发现，你采取的是笛卡尔式的产品。

scala> convert(Seq(Seq(1,2,3), Seq(4,5), Seq(6,7,8))) 
res: Seq[Seq[Int]] = List(List(1, 4, 6), List(1, 4, 7), List(1, 4, 8), 
List(1, 5, 6), List(1, 5, 7), List(1, 5, 8), List(2, 4, 6), List(2, 4, 7), 
List(2, 4, 8), List(2, 5, 6), List(2, 5, 7), List(2, 5, 8), List(3, 4, 6), 
List(3, 4, 7), List(3, 4, 8), List(3, 5, 6), List(3, 5, 7), List(3, 5, 8))

来源

2016-08-24 18:27:18 Alec

谢谢，这是我需要的。我将分解这个来理解它在做什么。 –

在理解中究竟是什么b：+ n在做什么？ –

'b：+ n'将元素'b'前置到Seq'n'。 – Alec

这是操纵列表（或您的案例中的序列）的标准递归概念。关键是要颠倒你的想法，并考虑你如何“建立”每个候选案例。请注意，正如另一个解决方案所示，解决这个问题的方法有很多，所有这些方法或多或少地相互缩减。

我在这里展示的解决方案是正确的，除了订购（故意）。它应该表现出必要的概念，虽然：

def process(input: Seq[Seq[Int]]): Seq[Seq[Int]] = input match { 
    case Nil => Seq() 
    case head :: Nil => head.map((element: Int) => Seq(element)) 
    case (head: Seq[Int]) :: tail => process(tail).flatMap(
    (tailSeq: Seq[Int]) => { 
     head.map((element: Int) => element +: tailSeq) 
    }) 

} 

// In the worksheet 
val processResult = process(input) // Visual inspection shows correctness 
processResult.length == (A.length * B.length * C.length) // Just verify we get the correct number of values

当考虑递归你应该做的第一件事是考虑你的基本情况。在这种情况下，如果input列表为空，会发生什么情况？我们知道这是一个空的Seq。这很有用，因为我们可以在其上构建我们的解决方案。现在，我作了一些小小的尝试，并提出了第二个基本案例（任何不递归的案例都是基本案例），我们只有一个序列：我们知道这个结果是一系列序列，其中每个序列都有一个单一的元素。

我们使用map构造这个，我们将输入序列（head）中的每个元素转换或“映射”为单元素序列。所有这些都是我们构建解决方案其余部分的基本序列。

假设的基础上，我们认为如果我们input（在tail）和一些新的序列（head）附加序列数目不详的会发生什么 - 这就是所谓的一般情况下。我们可以相信，process将返回所有其他序列的正确解决方案，因此我们通过process(tail)来完成。现在我们只需要采取并使用head进行转换。

再次，我们希望跨越所有的结果序列map。如果处理tail返回Seq(Seq(3), Seq(4))，并且我们的head是Seq(1,2)我们知道我们需要Seq(Seq(1,3), Seq(1,4), Seq(2,3), Seq(2,4)作为我们的结果。外部映射（实际上是flatMap）依次取得每个结果序列，并使用head序列中的每个元素使用map至prepend (+:)。

如果我们要使用map而不是flatMap，结果将是：Seq(Seq(Seq(1,3), Seq(1,4)), Seq(Seq(2,3), Seq(2,4)))。flatMap所做的只是简化了head映射，所以应用每个头元素的结果都以相同的顺序结束。（读者练习：如果第二map替换flatMap发生了什么？）

因此，考虑的tail正确的处理，我们知道我们可以添加任意的序列，并得到正确的输出。这就是所有需要的，以及递归的魔力！

来源

2016-08-24 20:26:13

斯卡拉 - 折叠多个Seqs

回答

相关问题