3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – pjdehez Nov 30 '18 at 14:25
2
$\begingroup$

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 *)
$\endgroup$
  • $\begingroup$ Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection. $\endgroup$ – Henrik Schumacher Nov 29 '18 at 16:40
  • 1
    $\begingroup$ I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs. $\endgroup$ – Jason B. Nov 29 '18 at 16:42
  • $\begingroup$ If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is. $\endgroup$ – Jason B. Nov 29 '18 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Henrik Schumacher Nov 29 '18 at 16:46
1
$\begingroup$
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

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – pjdehez Nov 30 '18 at 14:31

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.