代码之家 › 专栏 › 技术社区 › Abhijit Sarkar

如何将Seq的每个元素与其余元素配对?

scala-collections scala

Abhijit Sarkar · 技术社区 · 6 年前

我在寻找一种优雅的方式来组合 Seq 剩下的要收藏一大堆。例子: Seq(1,2,3).someMethod 应该产生类似

Iterator(
  (1,Seq(2,3)),
  (2,Seq(1,3)),
  (3,Seq(1,2))
)

元素的顺序无关紧要。它不一定是一个元组,一个 Seq(Seq(1),Seq(2,3)) 也可以接受(虽然有点难看)。

注意重点是大的集合(这就是我的示例显示 Iterator ). 还要注意的是,这不是 combinations .

思想?

编辑: 在我的用例中,数字应该是唯一的。如果一个解决方案可以消除重复,那很好,但不需要额外的成本。否则,可以接受欺骗。

最后,我选择了一个嵌套的 for -循环,并跳过了 i == j . 未创建新集合。我把正确而简单的解决办法投了赞成票( “简单是最复杂的” -达芬奇),但即使是最好的也只是二次问题的性质,一些创造中间集合的使用 ++ 我想避免,因为我处理的集合有接近50000个元素,25亿个元素。

5 回复 | 直到 6 年前

Andrey Tyukin 6 年前

以下代码具有恒定的运行时(它延迟地执行所有操作),但是访问结果集合的每个元素具有恒定的开销(当访问每个元素时,每次都必须计算索引移位):

def faceMap(i: Int)(j: Int) = if (j < i) j else j + 1

def facets[A](simplex: Vector[A]): Seq[(A, Seq[A])] = {
  val n = simplex.size
  (0 until n).view.map { i => (
    simplex(i),
    (0 until n - 1).view.map(j => simplex(faceMap(i)(j)))
  )}
}

println("Example: facets of a 3-dimensional simplex")
for ((i, v) <- facets((0 to 3).toVector)) {
  println(i + " -> " + v.mkString("[", ",", "]"))
}

输出:

Example: facets of a 3-dimensional simplex
0 -> [1,2,3]
1 -> [0,2,3]
2 -> [0,1,3]
3 -> [0,1,2]

这段代码用 simplices ,因为“省略一个索引”正好对应 face maps 对于组合描述的单纯形。为了进一步说明这个想法,下面是 faceMap 做:

println("Example: how `faceMap(3)` shifts indices")
for (i <- 0 to 5) {
  println(i + " -> " + faceMap(3)(i))
}

Example: how `faceMap(3)` shifts indices
0 -> 0
1 -> 1
2 -> 2
3 -> 4
4 -> 5
5 -> 6

这个 facets 方法使用 面图 s创建一个原始集合的惰性视图,该视图通过从被省略元素的索引开始将索引移动1来省略一个元素。

Jack Leow 6 年前

如果我正确地理解了您想要的内容,在处理重复值(即,要保留重复值)方面,下面是一些应该有效的方法。给定以下输入:

import scala.util.Random

val nums = Vector.fill(20)(Random.nextInt)

这应该能满足您的需求:

for (i <- Iterator.from(0).take(nums.size)) yield {
  nums(i) -> (nums.take(i) ++ nums.drop(i + 1))
}

另一方面,如果要删除DUP,我将转换为集合:

val numsSet = nums.toSet
for (num <- nums) yield {
  num -> (numsSet - num)
}

Dima 6 年前

seq.iterator.map { case x => x -> seq.filter(_ != x) }

这是二次的,但我不认为你能做的太多,因为最终,创建一个集合是线性的,你需要 N 他们中的一个。

Arnon Rotem-Gal-Oz 6 年前

import scala.annotation.tailrec

def prems(s : Seq[Int]):Map[Int,Seq[Int]]={
  @tailrec
  def p(prev: Seq[Int],s :Seq[Int],res:Map[Int,Seq[Int]]):Map[Int,Seq[Int]] = s match {
    case x::Nil => res+(x->prev)
    case x::xs=> p(x +: prev,xs, res+(x ->(prev++xs)))
  }

  p(Seq.empty[Int],s,Map.empty[Int,Seq[Int]])
}

prems(Seq(1,2,3,4))
res0: Map[Int,Seq[Int]] = Map(1 -> List(2, 3, 4), 2 -> List(1, 3, 4), 3 -> List(2, 1, 4),4 -> List(3, 2, 1))

-2

Carsten 6 年前

我想你在找 permutations . 可以将结果列表映射到要查找的结构中:

Seq(1,2,3).permutations.map(p => (p.head, p.tail)).toList
res49: List[(Int, Seq[Int])] = List((1,List(2, 3)), (1,List(3, 2)), (2,List(1, 3)), (2,List(3, 1)), (3,List(1, 2)), (3,List(2, 1)))

请注意,最终 toList 调用仅用于触发表达式的求值;否则,结果将是您要求的迭代器。

为了消除重复的头部, toMap 似乎是最直接的方法:

Seq(1,2,3).permutations.map(p => (p.head, p.tail)).toMap
res50: scala.collection.immutable.Map[Int,Seq[Int]] = Map(1 -> List(3, 2), 2 -> List(3, 1), 3 -> List(2, 1))