Co_42
Co_42

Reputation: 1269

Scala generate unique pairs from list

Input :

val list = List(1, 2, 3, 4)

Desired output :

Iterator((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4))

This code works :

for (cur1 <- 0 until list.size; cur2 <- (cur1 + 1) until list.size)
  yield (list(cur1), list(cur2))

but it not seems optimal, is there any better way of doing it ?

Upvotes: 12

Views: 5653

Answers (2)

Gianmario Spacagna
Gianmario Spacagna

Reputation: 1300

.combinations is the proper way for generating unique arbitrary groups of any size, another alternative solution that does not check the uniqueness in first place is using foldLeft that way:

val list = (1 to 10).toList

val header :: tail = list
tail.foldLeft((header, tail, List.empty[(Int, Int)])) {
  case ((header, tail, res), elem) =>
    (elem, tail.drop(1), res ++ tail.map(x => (header, x)))
}._3

Will produce:

res0: List[(Int, Int)] = List((1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10), (4,5), (4,6), (4,7), (4,8), (4,9), (4,10), (5,6), (5,7), (5,8), (5,9), (5,10), (6,7), (6,8), (6,9), (6,10), (7,8), (7,9), (7,10), (8,9), (8,10), (9,10))

If you expect there to be duplicates then you can turn the output list into a set and bring it back into a list, but you will lose the ordering then. Thus not the recommended way if you want to have uniqueness, but should be preferred if you want to generate all of the pairs included equal elements.

E.g. I used it in the field of machine learning for generating all of the products between each pair of variables in the feature space and if two or more variables have the same value I still want to produce a new variable corresponding to their product even though those newly generated "interaction variables" will have duplicates.

Upvotes: 0

acjay
acjay

Reputation: 36671

There's a .combinations method built-in:

scala> List(1,2,3,4).combinations(2).toList
res0: List[List[Int]] = List(List(1, 2), List(1, 3), List(1, 4), List(2, 3), List(2, 4), List(3, 4))

It returns an Iterator, but I added .toList just for the purpose of printing the result. If you want your results in tuple form, you can do:

scala> List(1,2,3,4).combinations(2).map{ case Seq(x, y) => (x, y) }.toList
res1: List[(Int, Int)] = List((1,2), (1,3), (1,4), (2,3), (2,4), (3,4))

You mentioned uniqueness as well, so you could apply .distinct to your input list uniqueness isn't a precondition of your function, because .combination will not deduplicate for you.

Upvotes: 27

Related Questions