10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ At this point it seems clear that the answer that makes the most sense depends on your data. Could you follow up and let us know: (1) Do you have repeated items in your "list" or is it a "set"/"permutation"? and (2) Do you expect to use this in a setting where most tests return True or most return False? $\endgroup$ – Kellen Myers Oct 20 '14 at 19:09
14
$\begingroup$

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

areListsEqual[List1_,List2_]:=(Sort[List1]===Sort[List2]);
$\endgroup$
12
$\begingroup$

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} *)
$\endgroup$
  • $\begingroup$ Ah, what I was thinking about, List complicates that. But I suppose this may work: Total[Join[h @@@ Tally[a], -h @@@ Tally[b]]] === 0. $\endgroup$ – Kuba Oct 20 '14 at 12:21
5
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ A very diligent and interesting analysis, +1 $\endgroup$ – eldo Oct 20 '14 at 11:20
2
$\begingroup$

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

 

$\endgroup$
  • 3
    $\begingroup$ This is slower than ybeltukov's orderlessSameQ and lalmei's areListsEqual. $\endgroup$ – kglr Jan 18 '18 at 5:45
1
$\begingroup$

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}]
  ]
$\endgroup$
  • $\begingroup$ Doesn't function with me. Could you produce some output? $\endgroup$ – eldo Oct 20 '14 at 20:00
  • $\begingroup$ @eldo, fogot TrueQ at the last line. And with this funtion work fine $\endgroup$ – molekyla777 Oct 20 '14 at 20:03
0
$\begingroup$
SameMembersQ[x_?VectorQ, y_?VectorQ] :=
 TrueQ[Permute[x, FindPermutation[x, y]] == y] // Quiet

SameMembersQ[{c, b, a}, #] & /@ {{a, c, b}, {a, c, x}, {a, c, a, a}}

{True, False, False}

$\endgroup$
0
$\begingroup$

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}
      *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.