Mở rộng Tập hợp [Đặt [Chuỗi]] thành Sản phẩm Cartesian trong Scala

Question

Tôi có tập hợp các bộ sau đây. Tôi không biết trước bao lâu nữa.

val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T")) 

tôi muốn mở rộng nó thành một sản phẩm Descartes:

Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T") 

Làm thế nào bạn sẽ làm điều đó?

Answer 1

Tôi nghĩ rằng tôi đã tìm ra cách để làm điều đó.

def combine(acc:Set[String], set:Set[String]) = for (a <- acc; s <- set) yield { 
    a + "&" + s 
} 

val expanded = sets.reduceLeft(combine) 

expanded: scala.collection.immutable.Set[java.lang.String] = Set(b&2&T, a&1&S, 
    a&1&T, b&1&S, b&1&T, c&1&T, a&2&T, c&1&S, c&2&T, a&2&S, c&2&S, b&2&S) 

Answer 2

Câu hỏi hay. Dưới đây là một cách:

scala> val seqs = Seq(Seq("a","b","c"), Seq("1","2"), Seq("S","T"))     
seqs: Seq[Seq[java.lang.String]] = List(List(a, b, c), List(1, 2), List(S, T)) 

scala> val seqs2 = seqs.map(_.map(Seq(_))) 
seqs2: Seq[Seq[Seq[java.lang.String]]] = List(List(List(a), List(b), List(c)), List(List(1), List(2)), List(List(S), List(T))) 

scala> val combined = seqs2.reduceLeft((xs, ys) => for {x <- xs; y <- ys} yield x ++ y) 
combined: Seq[Seq[java.lang.String]] = List(List(a, 1, S), List(a, 1, T), List(a, 2, S), List(a, 2, T), List(b, 1, S), List(b, 1, T), List(b, 2, S), List(b, 2, T), List(c, 1, S), List(c, 1, T), List(c, 2, S), List(c, 2, T)) 

scala> combined.map(_.mkString("&"))    
res11: Seq[String] = List(a&1&S, a&1&T, a&2&S, a&2&T, b&1&S, b&1&T, b&2&S, b&2&T, c&1&S, c&1&T, c&2&S, c&2&T) 

Answer 3

đưa ra sau khi batle;) nhưng có một khác:

sets.reduceLeft((s0,s1)=>s0.flatMap(a=>s1.map(a+"&"+_))) 

Answer 4

Mở rộng trên @Patrick's answer. Bây giờ là nói chung và lazier hơn:

def combine[A](f:(A, A) => A)(xs:Iterable[Iterable[A]]) = 
    xs.reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } } 

Có nó được lười biếng cho phép bạn tiết kiệm không gian, vì bạn không lưu trữ các mặt hàng theo cấp số nhân nhiều trong tập mở rộng; thay vào đó, bạn tạo ra chúng trên bay. Tuy nhiên, nếu bạn thực sự muốn tập hợp đầy đủ, bạn có thể vẫn nhận được nó như vậy:

val expanded = combine{(x:String, y:String) => x + "&" + y}(sets).toSet 

Answer 5

Mở rộng trên dsg's answer, bạn có thể viết nó rõ ràng hơn (tôi nghĩ) Bằng cách này, nếu bạn không nhớ các cà ri chức năng:

def combine[A](f: A => A => A)(xs:Iterable[Iterable[A]]) = 
    xs reduceLeft { (x, y) => x.view flatMap { y map f(_) } } 

Một thay thế (hơi dài, nhưng nhiều dễ đọc hơn):

def combine[A](f: (A, A) => A)(xs:Iterable[Iterable[A]]) = 
    xs reduceLeft { (x, y) => for (a <- x.view; b <- y) yield f(a, b) } 

Cách sử dụng:

combine[String](a => b => a + "&" + b)(sets) // curried version 

combine[String](_ + "&" + _)(sets)    // uncurried version