lista - Método de Scala para combinar cada elemento de un iterable con cada elemento de otro?

recorrer lista scala

Question

Si tengo esto:

val a = Array("a ","b ","c ")
val b = Array("x","y")

Me gustaría saber si existe un método de este tipo que me permita atravesar la primera colección, y para cada uno de sus elementos, recorrer toda la segunda colección. Por ejemplo, si tomamos la matriz a , tendríamos a,x , a,y , b,x , b,y , c,x , c,y . Sé de zip pero, por lo que he visto, solo funciona en colecciones del mismo tamaño y asocia elementos de las mismas posiciones.

Answer 1

No estoy seguro de un "método", pero esto se puede expresar con un compuesto / compuesto anidado for :

val a = Array("a ","b ","c ")
val b = Array("x","y")
for (a_ <- a; b_ <- b) yield (a_, b_)

res0: Array[(java.lang.String, java.lang.String)] = Array((a ,x), (a ,y), (b ,x), (b ,y), (c ,x), (c ,y))

Feliz codificación.

Answer 2

Para obtener una lista de un número desconocido de listas, de diferente longitud y para tal vez diferentes tipos, puede usar esto:

def xproduct (xx: List [List[_]]) : List [List[_]] = 
  xx match {
    case aa :: bb :: Nil => 
      aa.map (a => bb.map (b => List (a, b))).flatten       
    case aa :: bb :: cc => 
      xproduct (bb :: cc).map (li => aa.map (a => a :: li)).flatten
    case _ => xx
}

Lo llamarías

xproduct List (List ("a ", "b ", "c "), List ("x", "y"))

pero también puede llamarlo con listas de diferentes tipos:

scala>  xproduct (List (List ("Beatles", "Stones"), List (8, 9, 10), List (''$'', ''€'')))  
res146: List[List[_]] = List(List(Beatles, 8, $), List(Stones, 8, $), List(Beatles, 8, €), List(Stones, 8, €), List(Beatles, 9, $), List(Stones, 9, $), List(Beatles, 9, €), List(Stones, 9, €), List(Beatles, 10, $), List(Stones, 10, $), List(Beatles, 10, €), List(Stones, 10, €))

Las matrices se deben convertir en Listas y el resultado se debe volver a convertir en Matrices, si no se pueden usar Listas.

actualizar:

En el camino hacia una colección perezosa, realicé un mapeo funcional desde un índice (desde 0 hasta el tamaño de combinación - 1) hasta el resultado en esa posición, fácilmente calculado con módulo y división, solo se necesita una pequeña concentración:

def combicount (xx: List [List[_]]): Int = (1 /: xx) (_ * _.length)

def combination (xx: List [List[_]], i: Int): List[_] = xx match {
    case Nil => Nil
    case x :: xs => x(i % x.length) :: combination (xs, i / x.length)
}

def xproduct (xx: List [List[_]]): List [List[_]] = 
  (0 until combicount (xx)).toList.map (i => combination (xx, i))

No es problema usar un largo, o incluso BigInt.

actualización 2, el iterador:

class Cartesian (val ll: List[List[_]]) extends Iterator [List[_]] {

  def combicount (): Int = (1 /: ll) (_ * _.length)

  val last = combicount - 1 
  var iter = 0

  override def hasNext (): Boolean = iter < last
  override def next (): List[_] = {
    val res = combination (ll, iter)
    iter += 1
    res
  }

  def combination (xx: List [List[_]], i: Int): List[_] = xx match {
      case Nil => Nil
      case x :: xs => x (i % x.length) :: combination (xs, i / x.length) 
  }
}

Answer 3

Si desea mostrar su profundo conocimiento de los tipos de mayor grado y la teoría de categorías, puede escribir:

trait Applicative[App[_]] {
  def pure[A](a: A): App[A]
  def fmap[A,B](f: A => B, appA: App[A]): App[B]
  def star[A,B](appF: App[A => B], appA: App[A]): App[B]
}

object ListApplicative extends Applicative[List] {
  override def pure[A](a: A): List[A] = List(a)
  override def fmap[A,B](f: A => B, listA: List[A]): List[B] = listA.map(f)
  override def star[A,B](listF: List[A => B], listA: List[A]):List[B] = 
    for(f <- listF; a <- listA) yield f(a)
}

import ListApplicative._

def pairs[A,B](listA: List[A], listB: List[B]) = 
  star(fmap((a:A) => ((b:B) => (a,b)), listA), listB)

Aparte de eso, preferiría la solución de pst ...

Answer 4

Estoy usando lo siguiente extensivamente en mi código. Tenga en cuenta que esto funciona para una cantidad arbitraria de listas. Está creando un iterador en lugar de una colección, por lo que no tiene que almacenar el resultado potencialmente enorme en la memoria.

Cualquier mejora es bienvenida.

/**
  * An iterator, that traverses every combination of objects in a List of Lists.
  * The first Iterable will be incremented fastest. So consider the head as 
  * the "least significant" bit when counting.*/

class CombinationIterator[A](val components: List[Iterable[A]]) extends Iterator[List[A]]{
  private var state: List[BufferedIterator[A]] = components.map(_.iterator.buffered)
  private var depleted = state.exists(_.isEmpty)

  override def next(): List[A] = {
    //this function assumes, that every iterator is non-empty    
    def advance(s: List[(BufferedIterator[A],Iterable[A])]): List[(BufferedIterator[A],A)] = {
      if( s.isEmpty ){
        depleted = true
        Nil
      }
      else {
        assert(!s.head._1.isEmpty)

        //advance and return identity
        val it = s.head._1
        val next = it.next()
        if( it.hasNext){
          //we have simply incremented the head, so copy the rest
          (it,next) :: s.tail.map(t => (t._1,t._1.head))
        } else {
          //we have depleted the head iterator, reset it and increment the rest
          (s.head._2.iterator.buffered,next) :: advance(s.tail)
        }
      }
    }
    //zipping the iterables to the iterators is needed for resseting them
    val (newState, result) = advance(state.zip(components)).unzip

    //update state
    state = newState    

    result
  }

  override def hasNext = !depleted
}

Entonces, usando este, debe escribir el new CombinationIterator(List(a,b)) para obtener un iterador que pase por cada combinación.

Editar: basado en la versión desconocida del usuario

Tenga en cuenta que la siguiente versión no es óptima (en cuanto a rendimiento):

• acceso indexado en listas (use matrices en su lugar)
• takeWhile evalúa después de cada elemento

.

scala> def combination(xx: List[List[_]], i: Int): List[_] = xx match {
     | case Nil => Nil
     | case x :: xs => x(i % x.length) :: combination(xs, i/x.length)
     | }
combination: (xx: List[List[_]], i: Int)List[_]

scala> def combinationIterator(ll: List[List[_]]): Iterator[List[_]] = {
     | Iterator.from(0).takeWhile(n => n < ll.map(_.length).product).map(combination(ll,_))
     | }
combinationIterator: (ll: List[List[_]])Iterator[List[_]]

scala> List(List(1,2,3),List("a","b"),List(0.1,0.2,0.3))
res0: List[List[Any]] = List(List(1, 2, 3), List(a, b), List(0.1, 0.2, 0.3))

scala> combinationIterator(res0)
res1: Iterator[List[_]] = non-empty iterator

scala> res1.mkString("/n")
res2: String = 
List(1, a, 0.1)
List(2, a, 0.1)
List(3, a, 0.1)
List(1, b, 0.1)
List(2, b, 0.1)
List(3, b, 0.1)
List(1, a, 0.2)
List(2, a, 0.2)
List(3, a, 0.2)
List(1, b, 0.2)
List(2, b, 0.2)
List(3, b, 0.2)
List(1, a, 0.3)
List(2, a, 0.3)
List(3, a, 0.3)
List(1, b, 0.3)
List(2, b, 0.3)
List(3, b, 0.3)

Answer 5

Aquí hay uno más que hace lo mismo que la última edición de @ ziggystar, pero que no usa el acceso indexado de listas.

def combinationIterator[A](xs: Iterable[Iterable[A]]): Iterator[List[A]] = {
  xs.foldRight(Iterator(List[A]())) { (heads, tails) =>
    tails.flatMap { tail =>
      heads.map(head => head :: tail)
    }
  }
}

Y la versión azucarada:

def combinationIterator[A](xs: Iterable[Iterable[A]]): Iterator[List[A]] = {
  (xs :/ Iterator(List[A]())) { (heads, tails) =>
    for (tail <- tails; head <- heads) yield head :: tail
  }
}