如何将列表转换为类似的列表？

Question

假设我有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)) 
) 

Answer 1

“蛮力”：

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

Answer 2

有了一些索引，你可能得到的东西有点快于平均情况（而付出的一些额外的存储指数）：

首先我们为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）。