Как связать каждый элемент Seq с остальными?

Question

Я ищу элегантный способ объединить каждый элемент 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.

Идеи?

Редактировать: В моем случае использования номера должны быть уникальными.Если решение может устранить ошибки, это нормально, но не за дополнительную плату.В противном случае допустимы дуплексы.

Редактировать 2: В конце концов, я пошел с вложенным for -циклом и пропустил случай, когда i == j.Новые коллекции не были созданы.Я одобрил решения, которые были правильными и простыми ( «простота - высшая изощренность» - Леонардо да Винчи), но даже лучшие из них являются квадратичными просто по природе проблемы, а некоторые создают промежуточные коллекции поиспользование ++, которого я хотел избежать, потому что коллекция, с которой я имею дело, имеет около 50000 элементов, 2,5 миллиарда в квадратичном.

Answer 1

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 2

Если я правильно понимаю, что вы хотите, с точки зрения обработки повторяющихся значений (т. Е. Повторяющиеся значения должны быть сохранены), вот что должно работать.С учетом следующего ввода:

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

С другой стороны, если вы хотите удалить дубли, я бы преобразовал в Наборы:

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

Answer 3

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

Это квадратично, но я не думаю, что с этим можно многое сделать, потому что в конце дня создание коллекции является линейным, и вам понадобится Nих.

Answer 4

Следующий код имеет постоянное время выполнения (он делает все лениво), но доступ к каждому элементу результирующих коллекций имеет постоянные издержки (при доступе к каждому элементу смещение индекса должно вычисляться каждый раз):

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]

Этот код выражает все в терминах симплексов , поскольку «пропуск одного индекса» точно соответствует карты лиц для комбинаторно описанного симплекса.Чтобы дополнительно проиллюстрировать идею, вот что делает 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 использует faceMap s для создания ленивыхвид исходной коллекции, в которой пропущен один элемент путем смещения индексов на один, начиная с индекса пропущенного элемента.

Answer 5

Я думаю, что вы ищете 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))