Как проверить, есть ли пересечение в списке пар?

Question

У нас есть список пар, например следующим образом

val listPairs = List(("a", "a"), ("b", "a"), ("d", "d"), ("a", "c"))

Я хочу найти, существует ли i != j такое, что

listPairs(i)._1 = listPairs(j)._2

и напечатайте первый найденный i, j.

Так что для listPairs определенно есть i = 0, j = 1

Единственный способ, который я мог найти самостоятельно, - это просто просмотреть список для каждого индекса i, j, i < j и выполнить сравнение. Но это ужасный вложенный цикл с изменяемыми переменными.

Кто-нибудь может предложить лучший способ?

Answer 1

Слегка изменив ответ Лео, я использовал zipWithIndex, чтобы избежать доступа к спискам по индексу.

def checkIntersections[T](pairs: List[(T, T)]): List[(Int, Int)] = {
  val pairsWithIndex = pairs.zipWithIndex

  val result = for {
    ((a, _), i) <- pairsWithIndex
    ((_, b), j) <- pairsWithIndex
    if i != j && a == b
  } yield (i, j)

  result.toList
}

checkIntersections(List(("a", "a"), ("b", "a"), ("d", "d"), ("a", "c")))
// res0: List[(Int, Int)] = List((0,1), (3,0), (3,1))

Answer 2

Использование хвостовой рекурсии

val listPairs = List(("a", "a"), ("b", "c"), ("d", "d"), ("y", "a"))
def res(lst: List[(String,String)], count: Int): Option[(Int,Int)] = {
if (lst.isEmpty) return None
lst.tail.indexWhere(_._2 == lst.head._1) match {
  case -1 => res(lst.tail, count+1)
  case a: Int => Some((count,count+a+1))
}
}
println(res(listPairs, 0))

Вывод: немного ((0,3))

Answer 3

Вы можете использовать for-comprehension с guard, как показано ниже:

val listPairs = List(("a", "a"), ("b", "a"), ("d", "d"), ("a", "c"))

val sz = listPairs.size

for {
  i <- (0 until sz)
  j <- (0 until sz)
  if i != j && listPairs(i)._1 == listPairs(j)._2
} yield (i, j)
// res1: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((0,1), (3,0), (3,1))

В случае, если требуются только совпадения с i

for {
  i <- (0 until sz)
  j <- (i+1 until sz)
  if listPairs(i)._1 == listPairs(j)._2
} yield (i, j)
// res2: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((0,1))