Non-repeating distinct pair combinations from two scala lists

Question

I have two lists:

val l1 = List(1,2,3)

val l2 = List(1,2,4,5)

Combining these two lists, how do I obtain the following result?

List((1,1), (1,2), (1,4), (1,5), (2,2), (2,4), (2,5), (3,1), (3,2), (3,4), (3,5))

Note how only one of (2,1) or (1,2) is chosen. Order of the pairs doesn't matter. How do I compute the output efficiently given that the two input lists are large.

Thanks in advance.

Shaido · Accepted Answer · 2017-09-25T02:05:57.657

If the final order does not matter at all then you can use a Set which will automatically remove all duplicates. In this case, it is necissary to make sure the values in all tuples follow the same order. For example, make sure the values in the tuples are always in acsending order. Working example:

val l1 = List(1,2,3).toSet  // Convert one of the lists to a Set
val l2 = List(1,2,4,5)

val set = for {
  x <- l1
  y <- l2
  z = if (x<y) (x,y) else (y,x)
} yield z

This will give you a Set containing the requested tuples. The first list is converted to a Set before the for-comprehension, this makes the final result into a Set as well. The same logic can be written with map and filter instead if that is preferred.

Alternatively, you can use breakOut (explained very well in the answer here).

import scala.collection.breakOut
val set: Set[(Int, Int)] = 
  (for {
    x <- l1
    y <- l2
    z = if (x<y) (x,y) else (y,x)
  } yield z) (breakOut)

This will give the same results, but you do not need to convert one of your lists before the for comprehension.

Non-repeating distinct pair combinations from two scala lists

1 Answers1