Testing intersections in a list












3














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!










share|improve this question
























  • 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.
    – pjdehez
    Nov 30 at 14:25
















3














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!










share|improve this question
























  • 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.
    – pjdehez
    Nov 30 at 14:25














3












3








3







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!










share|improve this question















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!







list-manipulation






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 29 at 18:48









kglr

176k9197402




176k9197402










asked Nov 29 at 16:30









pjdehez

161




161












  • 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.
    – pjdehez
    Nov 30 at 14:25


















  • 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.
    – pjdehez
    Nov 30 at 14:25
















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.
– pjdehez
Nov 30 at 14:25




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.
– pjdehez
Nov 30 at 14:25










4 Answers
4






active

oldest

votes


















2














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 *)





share|improve this answer





















  • Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
    – Henrik Schumacher
    Nov 29 at 16:40








  • 1




    I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
    – Jason B.
    Nov 29 at 16:42










  • If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
    – Jason B.
    Nov 29 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.
    – Henrik Schumacher
    Nov 29 at 16:46





















1














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







share|improve this answer































    1














    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}







    share|improve this answer































      0














      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]





      share|improve this answer























      • 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.
        – pjdehez
        Nov 30 at 14:31











      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "387"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: false,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f186981%2ftesting-intersections-in-a-list%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      2














      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 *)





      share|improve this answer





















      • Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
        – Henrik Schumacher
        Nov 29 at 16:40








      • 1




        I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
        – Jason B.
        Nov 29 at 16:42










      • If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
        – Jason B.
        Nov 29 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.
        – Henrik Schumacher
        Nov 29 at 16:46


















      2














      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 *)





      share|improve this answer





















      • Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
        – Henrik Schumacher
        Nov 29 at 16:40








      • 1




        I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
        – Jason B.
        Nov 29 at 16:42










      • If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
        – Jason B.
        Nov 29 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.
        – Henrik Schumacher
        Nov 29 at 16:46
















      2












      2








      2






      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 *)





      share|improve this answer












      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 *)






      share|improve this answer












      share|improve this answer



      share|improve this answer










      answered Nov 29 at 16:37









      Jason B.

      47.6k387185




      47.6k387185












      • Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
        – Henrik Schumacher
        Nov 29 at 16:40








      • 1




        I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
        – Jason B.
        Nov 29 at 16:42










      • If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
        – Jason B.
        Nov 29 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.
        – Henrik Schumacher
        Nov 29 at 16:46




















      • Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
        – Henrik Schumacher
        Nov 29 at 16:40








      • 1




        I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
        – Jason B.
        Nov 29 at 16:42










      • If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
        – Jason B.
        Nov 29 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.
        – Henrik Schumacher
        Nov 29 at 16:46


















      Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
      – Henrik Schumacher
      Nov 29 at 16:40






      Also possible: MemberQ[DistanceMatrix[list, DistanceFunction -> IntersectingQ], Abs[False], {2}]. ;) In general, checking for intersection should be faster than computing the intersection.
      – Henrik Schumacher
      Nov 29 at 16:40






      1




      1




      I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
      – Jason B.
      Nov 29 at 16:42




      I was just noticing IntersectingQ in your post. I wish DistanceMatrix wasn't so stupid as to wrap the False with Abs.
      – Jason B.
      Nov 29 at 16:42












      If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
      – Jason B.
      Nov 29 at 16:44




      If IntersectingQ were implemented in the kernel it would indeed be faster, but it doesn't look like it is.
      – Jason B.
      Nov 29 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.
      – Henrik Schumacher
      Nov 29 at 16:46






      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.
      – Henrik Schumacher
      Nov 29 at 16:46













      1














      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







      share|improve this answer




























        1














        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







        share|improve this answer


























          1












          1








          1






          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







          share|improve this answer














          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








          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 29 at 17:04

























          answered Nov 29 at 16:37









          Henrik Schumacher

          48k466135




          48k466135























              1














              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}







              share|improve this answer




























                1














                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}







                share|improve this answer


























                  1












                  1








                  1






                  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}







                  share|improve this answer














                  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}








                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited Nov 30 at 8:56

























                  answered Nov 29 at 18:47









                  kglr

                  176k9197402




                  176k9197402























                      0














                      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]





                      share|improve this answer























                      • 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.
                        – pjdehez
                        Nov 30 at 14:31
















                      0














                      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]





                      share|improve this answer























                      • 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.
                        – pjdehez
                        Nov 30 at 14:31














                      0












                      0








                      0






                      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]





                      share|improve this answer














                      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]






                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      edited Nov 29 at 18:43

























                      answered Nov 29 at 18:37









                      Wen Chern

                      32118




                      32118












                      • 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.
                        – pjdehez
                        Nov 30 at 14:31


















                      • 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.
                        – pjdehez
                        Nov 30 at 14:31
















                      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.
                      – pjdehez
                      Nov 30 at 14:31




                      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.
                      – pjdehez
                      Nov 30 at 14:31


















                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematica Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f186981%2ftesting-intersections-in-a-list%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Berounka

                      Sphinx de Gizeh

                      Different font size/position of beamer's navigation symbols template's content depending on regular/plain...