Scala метод для объединения каждого элемента итерируемого с каждым элементом другого? - PullRequest
Новая
       24

Scala метод для объединения каждого элемента итерируемого с каждым элементом другого?

9 голосов
/ 11 мая 2011

Если у меня есть это: 

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

Я хотел бы знать, существует ли такой метод, который позволил бы мне пройти первую коллекцию, и для каждого из ее элементов пройти всю вторую коллекцию.Например, если мы возьмем массив a, мы получим a,x, a,y, b,x, b,y, c,x, c,y.Я знаю zip, но из того, что я видел, он работает только с коллекциями одинаковых размеров и связывает элементы с одинаковых позиций.

Ответы [ 5 ]

24 голосов
/ 11 мая 2011

Я не уверен в «методе», но это можно выразить только вложенным / составным 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))

Счастливым кодированием.

6 голосов
/ 11 мая 2011

Для списка неизвестного количества списков, разной длины и для, возможно, разных типов, вы можете использовать это: 

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
}

Вы бы назвали его 

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

но он также может вызывать списки другого типа: 

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

Массивы должны быть преобразованы в списки, а результат преобразован обратно в массивы, если вы не можете использовать списки.

обновление:

На пути к ленивой коллекции я сделал функциональное отображение из индекса (от 0 до размера комбинации - 1) на результат в этой позиции, легко вычисляемый по модулю и делению, простонужна битовая концентрация: 

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

Нет проблем использовать вместо long или даже BigInt.

обновление 2, Итератор: 

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) 
  }
}
5 голосов
/ 11 мая 2011

В своем коде я широко использую следующее.Обратите внимание, что это работает для произвольного числа списков.Он создает итератор вместо коллекции, поэтому вам не нужно хранить потенциально огромный результат в памяти.

Любые улучшения приветствуются. 

/**
  * 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
}

Так что, используя это, вы должны написать new CombinationIterator(List(a,b)), чтобы получить итератор, который проходит каждую комбинацию.

Редактировать: на основе версии unkown пользователя

Обратите внимание, что следующая версия не является оптимальной (с точки зрения производительности):

  • индексированный доступ к спискам (используйте вместо них массивы)
  • takeWhileоценивает после каждого элемента

. 

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)
4 голосов
/ 11 мая 2011

Если вы хотите похвастаться глубокими познаниями в теории типов и типов более высокого класса, вы можете написать: 

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)

Кроме этого, я бы предпочел решение pst ...

0 голосов
/ 13 февраля 2015

Вот еще одна вещь, которая делает то же самое, что и последнее редактирование @ ziggystar, но не использует индексированный доступ к спискам. 

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

И сладкая версия: 

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