Producto cartesiano de dos listas

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 en función de una secuencia de dígitos. Ejemplos:

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

Puedo hacer esto con respecto a las comprensiones

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

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

Genera todas las posibles secuencias de caracteres

 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án para secuencias de tres dígitos. ¿Hay alguna manera de lograr el mismo resultado para cualquier longitud de secuencia?

La siguiente sugerencia no es usar una comprensión for-exhaustiva. Pero no creo que sea una buena idea después de todo, porque como habrás notado, estarás atado a una cierta cantidad de tu 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 recursivo en la cola?

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 tengas muchas listas de singleton en xss . Este es el caso, porque el tamaño del resultado crece exponencialmente con la cantidad de elementos no únicos de xss .

Podría pensar en 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") 

Lo hice de la siguiente manera y funciona

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

No veo que el tipo de $ Tree que estoy tratando funciona para colecciones arbitrarias también …

    Intereting Posts