Testing intersections in a list











up vote
3
down vote

favorite












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









New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • 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















up vote
3
down vote

favorite












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









New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • 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













up vote
3
down vote

favorite









up vote
3
down vote

favorite











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









New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











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









New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited Nov 29 at 18:48









kglr

174k9196402




174k9196402






New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Nov 29 at 16:30









pjdehez

161




161




New contributor




pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






pjdehez is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • 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

















up vote
2
down vote













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




















up vote
1
down vote













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






























    up vote
    1
    down vote













    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






























      up vote
      0
      down vote













      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',
      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
      });


      }
      });






      pjdehez is a new contributor. Be nice, and check out our Code of Conduct.










      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








      up vote
      2
      down vote













      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

















      up vote
      2
      down vote













      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















      up vote
      2
      down vote










      up vote
      2
      down vote









      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.4k387185




      47.4k387185












      • 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












      up vote
      1
      down vote













      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



























        up vote
        1
        down vote













        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

























          up vote
          1
          down vote










          up vote
          1
          down vote









          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

          46.4k466133




          46.4k466133






















              up vote
              1
              down vote













              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



























                up vote
                1
                down vote













                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

























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  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

                  174k9196402




                  174k9196402






















                      up vote
                      0
                      down vote













                      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















                      up vote
                      0
                      down vote













                      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













                      up vote
                      0
                      down vote










                      up vote
                      0
                      down vote









                      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










                      pjdehez is a new contributor. Be nice, and check out our Code of Conduct.










                      draft saved

                      draft discarded


















                      pjdehez is a new contributor. Be nice, and check out our Code of Conduct.













                      pjdehez is a new contributor. Be nice, and check out our Code of Conduct.












                      pjdehez is a new contributor. Be nice, and check out our Code of Conduct.
















                      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

                      Plaza Victoria

                      Puebla de Zaragoza

                      Musa