Reputation: 1269
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
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
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