J'ai mis en œuvre une méthode simple pour générer un produit cartésien sur plusieurs évidemment, celui-ci est vraiment lent, car il calcule le tout produit à la fois. Quelqu'un a-t-il mis en œuvre une solution paresseuse pour ce problème dans Scala? P> OK, donc j'ai mis en œuvre une version stupide, mais une version de travail d'un itérateur sur un produit cartésien. Poster ici pour les passionnés futurs: P> SEQ code> s comme celui-ci: object RichSeq {
implicit def toRichSeq[T](s: Seq[T]) = new RichSeq(s)
}
class RichSeq[T](s: Seq[T]) {
def lazyCartesian(ss: Seq[Seq[T]]): Iterator[Seq[T]] = new Iterator[Seq[T]] {
private[this] val seqs = s +: ss
private[this] var indexes = Array.fill(seqs.length)(0)
private[this] val counts = Vector(seqs.map(_.length - 1): _*)
private[this] var current = 0
def next(): Seq[T] = {
val buffer = ArrayBuffer.empty[T]
if (current != 0) {
throw new NoSuchElementException("no more elements to traverse")
}
val newIndexes = ArrayBuffer.empty[Int]
var inside = 0
for ((index, i) <- indexes.zipWithIndex) {
buffer.append(seqs(i)(index))
newIndexes.append(index)
if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
inside = inside + 1
}
}
current = inside
if (current < seqs.length) {
for (i <- (0 to current).reverse) {
if ((0 to i).forall(ind => newIndexes(ind) == counts(ind))) {
newIndexes(i) = 0
} else if (newIndexes(i) < counts(i)) {
newIndexes(i) = newIndexes(i) + 1
}
}
current = 0
indexes = newIndexes.toArray
}
buffer.result()
}
def hasNext: Boolean = current != seqs.length
}
}
5 Réponses :
Ceux-ci pourraient être un point de départ:
Notez que une partie de la réponse de "Développer un ensemble [Set [String]] dans le produit cartésien dans Scala" est également paresseuse et prend beaucoup moins de code que ci-dessus.
Vous pouvez regarder ici: https://stackoverflow.com/a/8318364/312172 Comment traduire un numéro dans un index de toutes les valeurs possibles, sans générer tous les éléments.
Cette technique peut être utilisée pour implémenter un flux.
Vous pouvez définir le produit cartésien à l'aide des opérateurs existants sur les collections; Si vous convertissez la collecte en vues, la construction sera paresseuse. Voir ma réponse ci-dessous.
Voici ma solution au problème donné. Notez que la paresse est simplement causée par l'utilisation de pour obtenir ceci, j'ai commencé à partir de la fonction .View sur la "collection racine" de la compréhension utilisée. combiner défini dans https://stackoverflow.com/a/4515071/53974 , en passant La fonction (a, b) => (a, b) . Cependant, cela ne fonctionnait pas directement, car ce code attend une fonction de type (a, a) => A . Donc je viens de adapter le code un peu.
Qu'en est-il de: simple et paresseux;)
def cartesian[A](list: List[List[A]]): List[List[A]] = {
list match {
case Nil => List(List())
case h :: t => h.flatMap(i => cartesian(t).map(i :: _))
}
}
Au lieu de mettre en œuvre un produit paresseux à la main, essayez de réutiliser les collections paresseuses de Scala (flux et vues) - voir ci-dessous pour des liens vers des exemples.