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?

Improve this question
$\endgroup$
5
  • $\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
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 at 21:41
  • $\begingroup$ @ciao: in real cases there are only symbols into the lists. $\endgroup$
    – bobknight
    Commented Jun 6, 2015 at 21:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Complement[{a, b, b}, {a, b}] returns {} but the lists are not the same. $\endgroup$
    – ilian
    Commented Jun 6, 2015 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
    Commented Jun 6, 2015 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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