我有以下一組集。提前不知道多久。在Scala中將Set [Set [String]]展開爲笛卡爾積
val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T"))
我想將其擴展成笛卡爾乘積:
Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T")
你會如何做呢?
我有以下一組集。提前不知道多久。在Scala中將Set [Set [String]]展開爲笛卡爾積
val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T"))
我想將其擴展成笛卡爾乘積:
Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T")
你會如何做呢?
我想我想出瞭如何做到這一點。
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)
不錯的問題。這裏有一種方法:
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)
謝謝。我第一次嘗試foldLeft並最終想出我需要使用reduceLeft來代替(不斷得到一個空的結果)。轉換爲Seq只是爲了保持排序? – huynhjl 2010-05-23 16:02:39
最後的結合實際上是有幫助的,因爲這些集合實際上在同一個空間中,我需要將「b&a&a」合併到「a&b」中(刪除dups並排列組合)。 – huynhjl 2010-05-23 16:10:58
@huynhjl seq(開頭)的使用可能是爲了避免導入'scala.collection.immutable.Set',並且可能顯示這可以用更一般的接口完成。 – 2010-05-23 16:23:17
的batle後,來到;),但另一個問題:
sets.reduceLeft((s0,s1)=>s0.flatMap(a=>s1.map(a+"&"+_)))
擴展在@Patrick's answer。 現在是更普遍的和懶惰:
def combine[A](f:(A, A) => A)(xs:Iterable[Iterable[A]]) =
xs.reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } }
有它偷懶可以讓你節省空間,因爲你不存儲在擴展集的成倍許多項目;相反,您可以即時生成它們。但是,如果你真的想要全套,你仍然可以得到它像這樣:
val expanded = combine{(x:String, y:String) => x + "&" + y}(sets).toSet
下面是一個更通用的解決方案,可以在採用笛卡爾產品之前對地圖進行應用:http://stackoverflow.com/a/4515050/244526 – dsg 2011-12-19 06:15:25
擴展在dsg's answer,可以更清晰地寫出來(我認爲)這樣,如果你不介意的咖喱功能:
def combine[A](f: A => A => A)(xs:Iterable[Iterable[A]]) =
xs reduceLeft { (x, y) => x.view flatMap { y map f(_) } }
另一種替代方法(稍長,但更可讀):
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) }
用法:
combine[String](a => b => a + "&" + b)(sets) // curried version
combine[String](_ + "&" + _)(sets) // uncurried version
真棒,謝謝! – dsg 2010-12-23 05:13:42
同步性!在我的解決方案中,將字符串的構造推遲到最後一步,但它們基本相同。 – retronym 2010-05-23 15:59:20