30

Assuming:

val l1 = List(1,2,3) 
val l2 = List(2,3,1)

I want a method that confirms that l1 is equal to l2 (as in same contents but different order). Is there an API method on List/Seq to do this?

l1.sameElements(l2)

does not work as it verifies order as well.

I've come up with the following:

l1.foldLeft(l1.size == l2.size)(_ && l2.contains(_))

Is there anything more succinct than the above to do this comparison?

ssanj
  • 2,169
  • 3
  • 19
  • 28
  • http://stackoverflow.com/questions/2944617/use-example-of-scala-observableset-trait – James Black Sep 01 '10 at 23:46
  • How does the linked question relate to this question? – ssanj Sep 01 '10 at 23:58
  • Sets could solve his problem, but his comment to the answer below states he wants duplicates to be supported also, so Sets now won't work. – James Black Sep 02 '10 at 00:13
  • Yes, in the question, I check that the size of lists are equal. So basically the lists would have to be of equal size, duplicates or not. – ssanj Sep 02 '10 at 00:16

2 Answers2

55

If what you want is "these lists contain the same elements, irrespective of order or repetitions":

l1.toSet == l2.toSet

If what you want is "these lists contain the same elements, and with the same number of repetitions of each":

l1.sorted == l2.sorted

If what you want is "these lists contain the same elements and are the same size, but the number of repetitions of a given element can differ between the two lists":

l1.size == l2.size && l1.toSet == l2.toSet

Tom Crockett
  • 30,818
  • 8
  • 72
  • 90
  • I want to cater for duplicate elements as well. So List(1,2,3,3) should not equal (List(3,2,1)) – ssanj Sep 02 '10 at 00:00
  • List(1,2,3,3).sorted != List(3,2,1) – ssanj Sep 02 '10 at 00:15
  • I'm confused about what you want. You want to make sure that the exact same set of elements occurs the exact same number of times in each list, irrespective of order, right? – Tom Crockett Sep 02 '10 at 00:19
  • Sorry, I meant: List(1,2,3,3).sorted != List(3,2,1).sorted Yes, just the same number of elements and the same elements - could be in a different order. – ssanj Sep 02 '10 at 00:25
  • it sounds like you're saying you want the list to be the same size, but you don't care if the first list has 10 '3's and the second list has 4 '3's, just that they both have at least one '3' and the resulting list sizes are equal.... is that it? – Tom Crockett Sep 02 '10 at 00:28
  • btw, if you want `List(1,2,3,3)` to be considered equal to `List(3,2,1)` according to this hypothetical function, then comparing list sizes would rule that out... – Tom Crockett Sep 02 '10 at 00:32
  • List(1,2,3,3) does not equal List(3,2,1) in my prob. List(1,2,3,3) does equal List(3,1,2,3) tho. So they have to have: 1. The same number of elements (hence size does matter) 2. The same elements irrespective of order. – ssanj Sep 02 '10 at 00:38
  • but you don't care about the number of instances of a given element being the same between the two lists... if that's the case, then I would use `l1.size == l2.size && l1.toSet == l2.toSet` – Tom Crockett Sep 02 '10 at 00:42
  • I think my question may be confusing. I do care about the number of instances being the same, which means the length of each should be the same. Basically: List(1,2,3) should equal (List(3,2,1)), List(1,2,3,3) should equal (List(3,2,1,3), List(1,2,3,4) should not equal (List(3,2,1,3)), List(1,2,3,3,3) should not equal (List(3,2,1,3,4)), List(1,2,3,3,3) should not equal (List(3,2,1,3)) – ssanj Sep 02 '10 at 01:06
  • then you want `l1.sorted == l2.sorted` – Tom Crockett Sep 02 '10 at 01:21
10

While 

l1.sorted == l2.sorted

is correct, it's runtime performance is O(n log n), because of the sorting. For large lists, you are probably better with

l1.groupBy(identity) == l2.groupBy(identity)

which should be O(n), assuming a decent implementation of groupBy.

Dave Griffith
  • 20,435
  • 3
  • 55
  • 76
  • In Scala, I don't think the groupBy solution will work because the values of the map will be Arrays, and those will be compared using reference equality. `l1.groupBy(identity).mapValues(_.length) == ...` would work though. – csjacobs24 Oct 03 '16 at 15:35
  • I don't know if this was the case in 2016, but in Scala 2.12 and above, `groupBy`'s map will have values of the same type as the sequence. So if you run it on a List, you'll get a map of Lists, and comparing these by `equals` is just fine. – Jakub Kozłowski Mar 13 '23 at 20:52