Mark Jayxcela - 1 month ago 14x
Scala Question

# Cartesian product of two lists

Given a map where a digit is associated to several characters

``````scala> val conversion = Map("0" -> List("A", "B"), "1" -> List("C", "D"))
conversion: scala.collection.immutable.Map[java.lang.String,List[java.lang.String]] =
Map(0 -> List(A, B), 1 -> List(C, D))
``````

I want to generate all possible character sequences based on a sequence of digits. Examples:

``````"00" -> List("AA", "AB", "BA", "BB")
"01" -> List("AC", "AD", "BC", "BD")
``````

I can do this with for comprehensions

``````scala> val number = "011"
number: java.lang.String = 011
``````

Create a sequence of possible characters per index

``````scala> val values = number map { case c => conversion(c.toString) }
values: scala.collection.immutable.IndexedSeq[List[java.lang.String]] =
Vector(List(A, B), List(C, D), List(C, D))
``````

Generate all the possible character sequences

``````scala> for {
| a <- values(0)
| b <- values(1)
| c <- values(2)
| } yield a+b+c
res13: List[java.lang.String] = List(ACC, ACD, ADC, ADD, BCC, BCD, BDC, BDD)
``````

Here things get ugly and it will only work for sequences of three digits. Is there any way to achieve the same result for any sequence length?

The following suggestion is not using a for-comprehension. But I don't think it's a good idea after all, because as you noticed you'd be tied to a certain length of your cartesian product.

``````scala> def cartesianProduct[T](xss: List[List[T]]): List[List[T]] = xss match {
|   case Nil => List(Nil)
|   case h :: t => for(xh <- h; xt <- cartesianProduct(t)) yield xh :: xt
| }
cartesianProduct: [T](xss: List[List[T]])List[List[T]]

scala> val conversion = Map('0' -> List("A", "B"), '1' -> List("C", "D"))
conversion: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(0 -> List(A, B), 1 -> List(C, D))

scala> cartesianProduct("01".map(conversion).toList)
res9: List[List[java.lang.String]] = List(List(A, C), List(A, D), List(B, C), List(B, D))
``````
Source (Stackoverflow)