# Testing intersections in a list

In the following list {{1,3,5},{2,4,5},{3,4},{1,5}}, two elements have an empty intersection. This is not the case of the list {{1,4,5},{3,4,5},{3,4},{1,3}}. Is there a simple way to perform such a test? Thanks!

• Thanks to all of you. Great proposals. A priori, speed is not a consideration as far as it applies to lists of up to 6 elements (subsets), even if, in one case, the test has to be done about 60 millions of times... So it may matter and I am amazed by the differences in computation times between the different proposals. Commented Nov 30, 2018 at 14:25

One could compute all the intersections using DistanceMatrix, and test for the presence of an empty list

hasEmptyIntersectionQ[list_] := MemberQ[DistanceMatrix[list,
DistanceFunction -> Intersection], {}, {2}]

hasEmptyIntersectionQ@{{1, 4, 5}, {3, 4, 5}, {3, 4}, {1, 3}}
(* False *)

hasEmptyIntersectionQ@{{1, 3, 5}, {2, 4, 5}, {3, 4}, {1, 5}}
(* True *)

• Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection. Commented Nov 29, 2018 at 16:40
• I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs. Commented Nov 29, 2018 at 16:42
• If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is. Commented Nov 29, 2018 at 16:44
• Hmm. It seems that DistanceMatrix has some considerable overhead. Outer with IntersectingQ is an order of magnitude faster for this example. But fo longer input lists, DistanceMatrix with Intersection seems to be faster. I am puzzled. Commented Nov 29, 2018 at 16:46
f[list_List] := Not[And @@ Flatten[Outer[IntersectingQ, #, #, 1] &[list]]]

f[{{1, 3, 5}, {2, 4, 5}, {3, 4}, {1, 5}}]
f[{{1, 4, 5}, {3, 4, 5}, {3, 4}, {1, 3}}]


True

False

# Edit

Because I like SparseArrays a lot, here a variant involving SparseArray that solves this problem for lists of positive integers quite quickly:

h[list_List] := Module[{A},
A = SparseArray[
Join @@ MapIndexed[{x, i} \[Function] Thread[{x, i[[1]]}], list] -> 1
];
(A\[Transpose].A)["Density"] < 1.
]


A timing comparison:

a = Table[RandomInteger[{1, 10}, RandomInteger[{1, 10}]], {i, 1, 1000}];
r1 = f[a]; // AbsoluteTiming // First
r2 = hasEmptyIntersectionQ[a]; // AbsoluteTiming // First
r3 = h[a]; // AbsoluteTiming // First
r1 == r2 == r3


6.89991

2.73299

0.015683

True

Two additional ways, the first short and slow, the second ugly but fast:

ClearAll[hasDisjointPairQa, hasDisjointPairQb]
hasDisjointPairQa = Or @@ DisjointQ @@@ Subsets[#, {2}] &;

hasDisjointPairQb = Module[{a = False},
Do[If[DisjointQ[#[[i]], #[[j]]], a = True; Break[]],
{i, Length[#] - 1}, {j, i + 1, Length@#}]; a] &;

lists1 = {{1, 3, 5}, {2, 4, 5}, {3, 4}, {1, 5}};
lists2 = {{1, 4, 5}, {3, 4, 5}, {3, 4}, {1, 3}};
hasDisjointPairQ /@ {lists1, lists2}


{True, False}

hasDisjointPairQb /@ {lists1, lists2}


{True, False}

Timings using Henrik's setup (f and h are from Henrik's answer and hasEmptyIntersectionQ from Jason B.'s):

SeedRandom[1]
a = Table[RandomInteger[{1, 10}, RandomInteger[{1, 10}]], {i, 1, 1000}];

f[a] // AbsoluteTiming


{8.23578, True}

hasDisjointPairQa[a] // AbsoluteTiming


{4.10347, True}

hasEmptyIntersectionQ[a] // AbsoluteTiming


{3.08455, True}

h[a] // AbsoluteTiming


{0.0256391, True}

hasDisjointPairQb[a] // AbsoluteTiming


{0.000284839, True}

Frankly, I'm not quite clear about your question. If you want the testing function to return True only when any two elements of the list have nonempty intersection, Jason B. and Henrik Schumacher gave the correct answers. If you want the testing function to return True as far as there are two elements of the list have nonempty intersection, the following function would work:

f[x_]:=DuplicateFreeQ[x//Flatten]

• I wanted to have a testing function returning True whenever two elements (subsets) in the list have an empty intersection. I have so far used hasEmptyIntersection (by Jason) and h (by Henrik), the latter being definitely faster. Commented Nov 30, 2018 at 14:31