Scala - collapse multiple Seqs

Question

How can I transform a Seq[Seq[Int] such that each inner Seq contains the elements from the other two lists?

//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
}

Why don't you share some of you solutions with us as a starting point? — pedrofurla, Aug 24 '16 at 17:56
See this answer [here](http://stackoverflow.com/a/8218167/4496364). — insan-e, Aug 24 '16 at 17:56
It doesn't seem like anything is collapsing if you end up with more `Seq` objects than you start with. — Eric, Aug 24 '16 at 17:57
It think he wants to create permutations in the manner, that each inner Seq respresents a fixed position (1,2,3) at first position, (4,5) at the second position and so on. But please change the terminology (there is nothing collapsing) and provide your approaches. — sascha10000, Aug 24 '16 at 18:17

score 1 · Accepted Answer · answered Aug 24 '16 at 18:27

If this is a homework assignment, I recommend you don't turn in the following (you might to reverse engineer a simpler solution involving recursion out of it I guess). However, if you are really just curious about this, there are some pretty neat tricks.

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 emphasizes the fact that you will be starting from the left side of the input, working your way right one Seq at a time. Then, for every Seq you find, you take a cartesian product of sorts.

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

Thank you, this is what I needed. I will decompose this to understand what it is doing. — J.D., Aug 24 '16 at 18:38

score 0 · Answer 2 · answered Aug 24 '16 at 20:26

This is a standard recursive notion of manipulating a list of lists (or Sequences in your case). The key is to invert your thinking and consider how you 'build' each candidate case. Note that, as the other solution shows, there are several ways of solving this, all of which more or less reduce into each other.

The solution I show here is correct except for ordering (intentionally). It should show the necessary concepts, though:

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

When considering recursion the first thing you should do is consider your base case. In this case, what happens if the input list is empty? We know this to be an empty Seq. This is useful because we can build our solution on top of it. Now, I cheat a little and suggest a second base case (any case that doesn't recurse is a base case) where we have only a single sequence: we know that the result of this is a sequence of sequences, where each subsequence has a single element.

We use map to construct this, where we convert or 'map' each element in the input sequence (head) to a single-element sequence. All of these together is the base sequence we build the rest of our solution on.

Given that foundation, we consider what happens if there is an unknown number of additional sequences in our input (the tail) and some new sequence (the head) - this is called the general case. We can trust that process will return a correct solution for all the rest of those sequences, so we have it do that with process(tail). Now we just need to take that and transform it using head.

Again, we want to map across all of the resultant sequence. If processing the tail returned Seq(Seq(3), Seq(4)), and our head is Seq(1,2) we know we need a Seq(Seq(1,3), Seq(1,4), Seq(2,3), Seq(2,4) as our result. The outer map (actually flatMap) takes each of the resultant sequence in turn and uses map to prepend (+:) each element in the head sequence.

If we were to use map instead of flatMap the result would be: Seq(Seq(Seq(1,3), Seq(1,4)), Seq(Seq(2,3), Seq(2,4))). What flatMap does is simply 'flatten' the head mapping so the results of apply each head element all end up in the same sequence. (Exercise for the reader: what happens if the second map is replaced with flatMap?)

So, given a correct processing of tail we know we can add an arbitrary sequence and get a correct output. This is all that's needed, and the magic of recursion!

Scala - collapse multiple Seqs

2 Answers2