如何將列表轉換爲類似的列表？

假設我有A列表：如何將列表轉換爲類似的列表？

case class A(x: Int, y: Int) 
val as = List(A(0, 0), A(0, 1), A(1, 0), A(1, 1))

我想將其轉化爲對(A, Set[A])的列表，以便：

對的拳頭元素

名單as
在每一對(a, set)set由as這樣的項目組成x或y作爲a

例如：

val pairs = List(
    A(0, 0) -> Set(A(0, 1), A(1, 0)), 
    A(0, 1) -> Set(A(0, 0), A(1, 1)), 
    A(1, 0) -> Set(A(0, 0), A(1, 1)), 
    A(1, 1) -> Set(A(0, 1), A(1, 0)) 
)

來源

2017-04-16 Michael

「蠻力」：

case class A(x: Int, y: Int) 
val as = List(A(0, 0), A(0, 1), A(1, 0), A(1, 1)) 

val mappings = for { 
    a1 <- as 
    a2 <- as 
    if (a1 != a2) 
    if (a1.x == a2.x || a1.y == a2.y) 
} yield a1 -> a2 

val result = mappings.groupBy(_._1).mapValues(_.map(_._2))

來源

2017-04-16 16:53:21

小列表已經夠用了，謝謝。我只是想知道是否有可能比'O（N^2）'更有效地做到這一點' – Michael

我想我幾乎沒有。雖然你可以避免在最後使用可變映射進行分組和映射。 –

我非常喜歡不可變的集合。無論如何感謝您的建議。 – Michael

有了一些索引，你可能得到的東西有點快於平均情況（而付出的一些額外的存儲指數）：

首先我們爲X和Y創建一個索引：

val xi = as.groupBy(_.x) // O(n) 
val yi = as.groupBy(_.y) // O(n)

然後我們做一個單次使用的索引地圖中的每個元素：

// This is essentially O(n^2) worst case, but it can be much less if the toSet doesn't have to go through a lot each time 
val inter = for(a <- as) yield 
    (a, (xi.get(a.x).toSet ++ yi.get(a.y).toSet).flatten)

最後，你可能想從集刪除相同的元素鍵：

inter.map(x => (x._1, x._2 - x._1)) // O(n)

所以總的來說，這仍然是最壞情況O（n^2），但是在索引足夠稀疏的情況下，它可以基本上是O（n）。

來源

2017-04-17 06:52:44 marios

如何將列表轉換爲類似的列表？

回答

相關問題