I have two lists: excluded and values. I would like to efficiently determine whether excluded and values are disjoint. How does one go about doing this (preferably using FreeQ)?


In version 10.0 you have DisjointQ (and conversely IntersectingQ) to test this. 10.2 adds the Contains* family of function with ContainsNone being equivalent to DisjointQ. For earlier versions you could build this yourself:

disjointQ[a_List, b_List] := Intersection[a, b] === {}

disjointQ[{1, 2, 3}, {6, 4, 5}]
(* True *)

disjointQ[{1, 2, 3}, {1, 4, 5}]
(* False *)

I'd expect this might be faster than intersection on larger lists:

With[{j = Join[DeleteDuplicates@#1, DeleteDuplicates@#2]}, DeleteDuplicates@j == j] &[l1, l2]

Addendum - a little testing, does seem to have advantage when both lists large, otherwise a bit of a wash between this and using intersection... perhaps others can test on non-loungbook environments - I get wildly varying results depending on how I produce the random test lists :-|

Addendum 2: Per comments, differences were from packed/unpacked lists, and in my limited tests the above is faster for unpacked... carry on...

  • $\begingroup$ Could you give an example of the wildly varying results? I presume it's not simply packed vs. unpacked? $\endgroup$ – Mr.Wizard Jul 6 '15 at 17:04
  • $\begingroup$ @Mr.Wizard: {l1,l2}=Random[...,{2,x}] vs l1=Random[...,x];l2=Random[...,x], for example - I'd imagine is cache related on the hampsterbox... $\endgroup$ – ciao Jul 6 '15 at 17:15
  • $\begingroup$ And you are running 10.1.0? (Referring to Why does list assignment with a packed array result in unpacked values?) $\endgroup$ – Mr.Wizard Jul 6 '15 at 17:19
  • $\begingroup$ @Mr.Wizard: Nope, 10.x still on my voodoo list. And herp-a-derp on my part - could have sworn I checked packing when I got differing results and both cases were unpacked, appears I inadvertently tested same set, so that explains it. $\endgroup$ – ciao Jul 6 '15 at 17:22

While highly inefficient you asked about FreeQ and you could do this:

f0 = FreeQ[#, Alternatives @@ #2] &;

More practically here is a condensed version of rasher/ciao's method:

f1 = DuplicateFreeQ[Join @@ DeleteDuplicates /@ {##}] &

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.