Cartesian product of two lists
Solution 1
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))
Why not tail-recursive?
Note that above recursive function is not tail-recursive. This isn't a problem, as xss
will be short unless you have a lot of singleton lists in xss
. This is the case, because the size of the result grows exponentially with the number of non-singleton elements of xss
.
Solution 2
I could come up with this:
val conversion = Map('0' -> Seq("A", "B"), '1' -> Seq("C", "D"))
def permut(str: Seq[Char]): Seq[String] = str match {
case Seq() => Seq.empty
case Seq(c) => conversion(c)
case Seq(head, tail @ _*) =>
val t = permut(tail)
conversion(head).flatMap(pre => t.map(pre + _))
}
permut("011")
Related videos on Youtube
Comments
-
Mark Jayxcela almost 2 years
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?
-
Vlad Patryshev almost 10 yearsStrictly speaking, what you are trying to get is not a cartesian product. If you have
List[T]
, you do not guarantee the size, and also the list should be homogeneous.
-
-
Mark Jayxcela over 12 yearsThanks Sciss, I accepted ziggystar's answer since he posted it before and both answers are pretty good. I especially like your idea of decomposing the
for
in a chain offlatMaps
. -
ziggystar over 12 years@Mark Sciss' answer differs only syntactically from mine (at least for the part building the combinations). He uses
map
andflatMap
and I use the for-comprehension syntactic sugar, which gets translated to Sciss' code by the compiler. Only other difference is that I have extracted a method for the cartesian product. -
Mark Jayxcela over 12 years@ziggystar Great, now I understand better what is happening behind the scenes.