Check if two lists are equal in any order

Question

Suppose I have two lists, how can I efficiently check if the two lists are identical up to permutations of the elements?

For example I would like the function to output:

AreListsEqual[{a,b,c},{a,c,b}] = True
AreListsEqual[{a,b,c},{a,b,d}] = False
AreListsEqual[{a,b,c},{a,c,b,d}] = False

Update: In response to a comment by @KellenMyers, it does appear the best way to do this depends on the particular sets that are being compared. I am looking at comparing two sets that

1. About 1%-50% of the tests will return false.
2. Very few repeated items in the list

where most of the results will return false.

Answer 1

Is it any permutation ? Then I think then this should do

areListsEqual[List1_,List2_]:=(Sort[List1]===Sort[List2]);

Answer 2

If you have many duplicates (and the number of duplicates matter) then Tally can improve performance sufficiently

orderlessSameQ[a_List, b_List] := (Length@a == Length@b) && (Sort@Tally@a === Sort@Tally@b);

a = RandomInteger[{0, 1000}, 1000000];
b = RandomSample[a];

areListsEqual[a, b] // AbsoluteTiming (* lalmei *)
orderlessSameQ[a, b] // AbsoluteTiming
(* {0.577613, True} *)
(* {0.011876, True} *)

Answer 3

The Permutations method will be unnecessarily slow, but if you are talking about elements of a set (I'm not sure -- your terminology isn't clear), you can speed things up if you are expecting to see mostly False as output by doing the following:

areListsEqual[s1_, s2_] := Module[{i = 1, n = Length[s1]},
 If[Not[n == Length[s2]], Return[False]];
 While[i < n, If[Not[MemberQ[s2, s1[[i]], 1]], Return[False]]; i++;];
 Return[True];
];

Note that I'm using levelspec 1 in the MemberQ command, so that if you have lists of lists this still makes some sense. If you compare this with the other method, it might not be noticeable:

areListsEqual2[List1_, List2_] := (Sort[List1] === Sort[List2]);
Timing[areListsEqual[{a, b, c}, {c, b, a}]]
Timing[areListsEqual2[{a, b, c}, {c, b, a}]]

(* Output:
 {0., True}
 {0., True} *)

However, you'll see it on larger lists, whether they are different:

s1 = DeleteDuplicates[RandomInteger[10^10, 10^7]];
s2 = Take[DeleteDuplicates[RandomInteger[10^10, 2*10^7]], Length[s1]];
Timing[areListsEqual[s1, s2]]
Timing[areListsEqual2[s1, s2]]

(* Output:
 {0.717605, False}
 {3.900025, False} *)

and of course, the opposite result if they are actually equal:

s1 = DeleteDuplicates[RandomInteger[10^10, 10^4]];
s2 = {}; iv = Range[Length[s1]];
While[iv != {},
 i = RandomInteger[{1, Length[iv]}];
 s2 = Append[s2, s1[[iv[[i]]]]];
 iv = Drop[iv, {i}];
];
Timing[areListsEqual[s1, s2]]
Timing[areListsEqual2[s1, s2]]

(* Output:
 {1.466409, True}
 {0., True} *)

Note that in any event, when the two lists are longer, both methods take much longer (which is why I've restricted that one to size $10^4$ and not $10^7$. Even using a set size of roughly $10^5$.

And of course, when they actually don't agree in length, it's much easier to see:

s1 = DeleteDuplicates[RandomInteger[10^10, 10^7]];
s2 = Take[DeleteDuplicates[RandomInteger[10^10, 2*10^7]], Length[s1] + 1];
Timing[areListsEqual[s1, s2]]
Timing[areListsEqual2[s1, s2]]

(* Output:
 {0., False}
 {3.884425, False} *)

And can you imagine comparing a list of size $10^{10}$ with one of size $10^{10}+1$? You'd have to sort each one just to decide they aren't equal! Of course, who has the RAM for that?

So if you are expecting lots of lists to go through this that are clearly and obviously not the same, with lots of False output, you might want to try this method. If you are expecting to generally see lists that are the same or almost exactly the same (or which have repeated elements -- something I could, but have not, accounted for), you can stick to the Sort and === method. And of course, if your lists are of relatively small size, the question of efficiency is moot anyway.

Last minute note: I just saw eldo's answer, and I will note that his method is even slower than the Sort and === method in the case of False output. His time is 4.383628 for that first legitimate comparison and 4.274427 for the second (when the lists are different sizes). It also clocks in at 0. in the case where my method is slower (i.e. the True output).

Answer 4

OrderlessPatternSequence

orderlessMatchQ = MatchQ[#, {OrderlessPatternSequence @@ #2}] &;

Examples:

orderlessMatchQ[{a, b, c}, {a, c, b}] 

True

orderlessMatchQ[{a, c, b}, {a, b, c}] 

True

orderlessMatchQ[{a, b, c}, {a, b, d}] 

False

orderlessMatchQ[{a, b, c}, {a, c, b, d}]

False

 

Answer 5

Using UniqueElements (new in 13.1)

SameElements[a_][b_] := Flatten @ UniqueElements[{a, b}] == {}

SameElements[{a, b, c}] /@ {{a, c, b}, {a, b, d}, {a, c, b, d}}

{True, False, False}

Answer 6

Another possibility is to use Counts and ContainsOnly as follows:

SameElements[a_, b_] := ContainsOnly[Counts[Join[a, b]], {2}]

SameElements[{a, b, c}, #] & /@ {{a, c, b}, {a, b, d}, {a, c, b, d}}

(*{True, False, False}*)

SameElements[{1, 1, 2}, {1, 2, 2}]

(*False*)

SameElements[{a, b, c}, {a, b, b}]

(*False*)

Answer 7

Here is elegant way. Not fast but pretty

func[lst1_List, lst2_List] := Module[{f1, f2, x},
  SetAttributes[f1, Orderless];
  SetAttributes[f2, Orderless];
  f1[x__] := x;
  f2[x__] := x;
  TrueQ[{f1 @@ lst1} == {f2 @@ lst2}]
  ]

Answer 8

Using the Complement function, we can define AreListsEqual very simply as:

    AreListsEqual[list1_, list2_] := 
      Complement[list1, list2] == Complement[list2, list1];

Duplicates in each list are ignored. Hence, for example,

    AreListsEqual[{a,a,b}, {a,b}] == True

Unfortunately, if the lists are large, it's quite slow. Using @Kellen-Myers' lists,

    s1 = DeleteDuplicates[RandomInteger[10^10, 10^7]];
    s2 = Take[DeleteDuplicates[RandomInteger[10^10, 2*10^7]], Length[s1] + 1];
    Timing[AreListsEqual[s1, s2]]
     (* Output: 
         {10.0881, False}
      *)