斯卡拉 - 摺疊多個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

回答

相關問題