How to pair each element of a Seq with the rest?

Question

I'm looking for an elegant way to combine every element of a Seq with the rest for a large collection. Example: Seq(1,2,3).someMethod should produce something like

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

Order of elements doesn't matter. It doesn't have to be a tuple, a Seq(Seq(1),Seq(2,3)) is also acceptable (although kinda ugly).

Note the emphasis on large collection (which is why my example shows an Iterator). Also note that this is not combinations.

Ideas?

Edit: In my use case, the numbers are expected to be unique. If a solution can eliminate the dupes, that's fine, but not at additional cost. Otherwise, dupes are acceptable.

Edit 2: In the end, I went with a nested for-loop, and skipped the case when i == j. No new collections were created. I upvoted the solutions that were correct and simple ("simplicity is the ultimate sophistication" - Leonardo da Vinci), but even the best ones are quadratic just by the nature of the problem, and some create intermediate collections by usage of ++ that I wanted to avoid because the collection I'm dealing with has close to 50000 elements, 2.5 billion when quadratic.

Answer 1

The following code has constant runtime (it does everything lazily), but accessing every element of the resulting collections has constant overhead (when accessing each element, an index shift must be computed every time):

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

Example:

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

Output:

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

This code expresses everything in terms of simplices, because "omitting one index" corresponds exactly to the face maps for a combinatorially described simplex. To further illustrate the idea, here is what the faceMap does:

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

gives:

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

The facets method uses the faceMaps to create a lazy view of the original collection that omits one element by shifting the indices by one starting from the index of the omitted element.

Answer 2

If I understand what you want correctly, in terms of handling duplicate values (i.e., duplicate values are to be preserved), here's something that should work. Given the following input:

import scala.util.Random

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

This should get you what you need:

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

On the other hand, if you want to remove dups, I'd convert to Sets:

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

Answer 3

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

This is quadratic, but I don't think there is very much you can do about that, because in the end of the day, creating a collection is linear, and you are going to need N of them.

Answer 4

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

Answer 5

I think you are looking for permutations. You can map the resulting lists into the structure you are looking for:

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

Note that the final toList call is only there to trigger the evaluation of the expressions; otherwise, the result is an iterator as you asked for.

In order to get rid of the duplicate heads, toMap seems like the most straight-forward approach:

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