7
$\begingroup$

I have to compare two or more lists and check if they are the same, but their elements can be in different position. For instance

l1 = {a,b,c}
l2 = {b,c,a}

SameQ[l1, l2] 

(* False *)

but I need True.

The shortest way I can think about is

SameQ[Sort[l1], Sort[l2]] 

(* True *)

but having to compare many lists and sometimes they are really huge, I don't want to sort. Is there a built-in function or a better way to get that result?

$\endgroup$
  • $\begingroup$ I don't think there is a faster way (in terms of $O$). You can have some heuristics, but otherwise you won't have faster code than $O(n \log n)$. $\endgroup$ – m0nhawk Jun 6 '15 at 19:53
  • $\begingroup$ @m0nhawk thanks for the quick reply. I agree with you that in terms of O the complexity should be that of Sort, but in terms of implementation, if there is a native function embedded in the kernel it could be faster than a couple of Sort applied to huge list. I'm not sure but it could be. $\endgroup$ – bobknight Jun 6 '15 at 19:58
  • $\begingroup$ You can try to use Complement, but I'm not sure if it would be faster (and check if it's empty). $\endgroup$ – m0nhawk Jun 6 '15 at 20:15
  • 1
    $\begingroup$ More details on characteristics of lists might be useful - e.g., if they're symbols, strings, integers, reals, mixed, distinct elements or are duplications allowed, etc. There are very fast methods for specific use cases... $\endgroup$ – ciao Jun 6 '15 at 21:41
  • $\begingroup$ @ciao: in real cases there are only symbols into the lists. $\endgroup$ – bobknight Jun 6 '15 at 21:43
1
$\begingroup$

Using Complement on two lists could be used as follows:

Complement[l1, l2] == {}

True

If you have more than one list, for example,

l1 = {a, b, c};
l2 = {b, c, a};
l3 = {c, b, z};

you could also implement it with Tuples and compare the lists pairwise:

((Complement @@ #) == {}) & /@ Tuples[{l1, l2, l3}, 2]

{True, True, False, True, True, False, False, False, True}

Of course, you can also do this all in one go:

And @@ (((Complement @@ #) == {}) & /@ Tuples[{l1, l2, l3}, 2])

False

It's not elegant, and I'm skeptical about the efficiency.

$\endgroup$
  • 2
    $\begingroup$ Complement[{a, b, b}, {a, b}] returns {} but the lists are not the same. $\endgroup$ – ilian Jun 6 '15 at 20:38
  • $\begingroup$ Unfortunately Complement is not always correct for my purpose (as also pointed out by ilian), and even when it is, the AbsoluteTiming registered is more or less the same of the two Sort. $\endgroup$ – bobknight Jun 6 '15 at 20:40

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.