cross product of arbitrary number of lists in scala

Question

I have a list of lists in Scala as follows.

val inputList:List[List[Int]] = List(List(1, 2), List(3, 4, 5), List(1, 9))

I want a list of cross products of all the sub-lists.

val desiredOutput: List[List[Int]] = List( 
        List(1, 3, 1), List(1, 3, 9),
        List(1, 4, 1), List(1, 4, 9),
        List(1, 5, 1), List(1, 5, 9),
        List(2, 3, 1), List(2, 3, 9),
        List(2, 4, 1), List(2, 4, 9),
        List(2, 5, 1), List(2, 5, 9))

The number of elements in inputList as well as the sublist are not fixed. What is the Scala way of doing this?

Christopher Chiche · Answer 1 · 2012-11-26T15:53:56.670

Here is a method that works using recursion. However it is not tail recursive so beware of stackoverflows. However it can be transformed to a tail recursive function by using an auxiliary function.

def getProduct(input:List[List[Int]]):List[List[Int]] = input match{
  case Nil => Nil // just in case you input an empty list
  case head::Nil => head.map(_::Nil) 
  case head::tail => for(elem<- head; sub <- getProduct(tail)) yield elem::sub
}

Test:

scala> getProduct(inputList)
res32: List[List[Int]] = List(List(1, 3, 1), List(1, 3, 9), List(1, 4, 1), List(1, 4, 9), List(1, 5, 1), List(1, 5, 9), List(2, 3, 1), List(2, 3, 9), List(2, 4, 1), List(2, 4, 9), List(2, 5, 1), List(2, 5, 9))

score 4 · Accepted Answer · edited May 23 '17 at 11:53

4

If you use scalaz, this may be a suitable case for Applicative Builder:

import scalaz._
import Scalaz._

def desiredOutput(input: List[List[Int]]) = 
  input.foldLeft(List(List.empty[Int]))((l, r) => (l |@| r)(_ :+ _))

desiredOutput(List(List(1, 2), List(3, 4, 5), List(1, 9)))

I am not very familiar with scalaz myself, and I expect it has some more powerful magic to do this.

Edit

As Travis Brown suggest, we just write

def desiredOutput(input: List[List[Int]]) = input.sequence

And I find the answers of this question very helpful for understanding what sequence does.

edited May 23 '17 at 11:53

Community

1
1

answered Nov 26 '12 at 16:04

xiefei

6,443
2
24
43

thanks. looks elegant..but scary at the same time! will learn scalaz after I master basic Scala. – dips Nov 26 '12 at 16:26
1

You're right about more powerful magic: this is in fact just sequencing the top-level list, so you can write `input.sequence` here. – Travis Brown Nov 27 '12 at 21:30
This is very very cool ... like OMG scala & scalaz so clearly pwns every other language in the universe. I would love to see a similar thing done LAZILY!!! I.e. for `Iterator[Iterator[T]]` that returns `Iterator[Iterator[T]]` – samthebest Feb 01 '15 at 21:49
FYI, if you want to terse it up a bit you can do: `(List(List.empty[Int]) /: input)(_ |@| _ |> (_(_ :+ _)))` ... in fact I kinda wish `sequence` didn't exist just so I would have an excuse to use such code. – samthebest Feb 01 '15 at 22:08

score 2 · Answer 3 · answered Jun 12 '17 at 09:42

2

If you don't mind a bit of functional programming:

def cross[T](inputs: List[List[T]]) : List[List[T]] = 
    inputs.foldRight(List[List[T]](Nil))((el, rest) => el.flatMap(p => rest.map(p :: _)))

Much fun finding out how that works. :-)

answered Jun 12 '17 at 09:42

Hans-Peter Störr

24,220
27
98
136

this is insane! – botkop Sep 07 '17 at 12:49
@botkop Not really. Scala is for professional programmers that are used to it, of course. If you know Scala and functional programming decently well, this is a very clear and understandable way to describe the algorithm. – Hans-Peter Störr Sep 07 '17 at 19:02

score 1 · Answer 4 · answered Nov 26 '12 at 16:22

After several attempts, I arrived at this solution.

val inputList: List[List[Int]] = List(List(1, 2), List(3, 4, 5), List(1, 9))
val zss: List[List[Int]] = List(List())
def fun(xs: List[Int], zss: List[List[Int]]): List[List[Int]] = {
    for {
        x <- xs
        zs <- zss
    } yield {
        x :: zs
    }
}
val crossProd: List[List[Int]] = inputList.foldRight(zss)(fun _)
println(crossProd)

cross product of arbitrary number of lists in scala

4 Answers4