scala - propiedades - producto cartesiano relaciones y funciones

Producto cartesiano de dos listas.

Question

Dado un mapa donde un dígito está asociado a varios caracteres

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

Quiero generar todas las secuencias de caracteres posibles basadas en una secuencia de dígitos. Ejemplos:

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

Puedo hacer esto con comprensiones

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

Crea una secuencia de posibles caracteres por índice.

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

Generar todas las secuencias de caracteres posibles.

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)

Aquí las cosas se ponen feas y solo funcionará para secuencias de tres dígitos. ¿Hay alguna manera de lograr el mismo resultado para cualquier longitud de secuencia?

Answer 1

Acabo de hacer eso como sigue y funciona.

 def cross(a:IndexedSeq[Tree], b:IndexedSeq[Tree]) = {
a.map (p => b.map( o => (p,o))).flatten
}

No vea el tipo de $ Tree que lo estoy vendiendo, también funciona para colecciones arbitrarias ..

Answer 2

La siguiente sugerencia no es utilizar una comprensión para. Pero no creo que sea una buena idea después de todo, porque como notó, estaría atado a cierta longitud de su producto cartesiano.

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

¿Por qué no la cola recursiva?

Tenga en cuenta que la función recursiva anterior no es recursiva de cola. Esto no es un problema, ya que xss será corto a menos que tenga muchas listas singleton en xss . Este es el caso, porque el tamaño del resultado crece exponencialmente con el número de elementos no singleton de xss .

Answer 3

Podría llegar a esto:

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