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!
list-manipulation
add a comment |
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!
list-manipulation
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
add a comment |
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!
list-manipulation
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
list-manipulation
edited Nov 29 at 18:48
kglr
175k9197402
175k9197402
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
add a comment |
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
add a comment |
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 *)
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 noticingIntersectingQ
in your post. I wishDistanceMatrix
wasn't so stupid as to wrap theFalse
withAbs
.
– Jason B.
Nov 29 at 16:42
IfIntersectingQ
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 thatDistanceMatrix
has some considerable overhead.Outer
withIntersectingQ
is an order of magnitude faster for this example. But fo longer input lists,DistanceMatrix
withIntersection
seems to be faster. I am puzzled.
– Henrik Schumacher
Nov 29 at 16:46
add a comment |
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 SparseArray
s 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
add a comment |
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}
add a comment |
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]
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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 *)
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 noticingIntersectingQ
in your post. I wishDistanceMatrix
wasn't so stupid as to wrap theFalse
withAbs
.
– Jason B.
Nov 29 at 16:42
IfIntersectingQ
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 thatDistanceMatrix
has some considerable overhead.Outer
withIntersectingQ
is an order of magnitude faster for this example. But fo longer input lists,DistanceMatrix
withIntersection
seems to be faster. I am puzzled.
– Henrik Schumacher
Nov 29 at 16:46
add a comment |
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 *)
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 noticingIntersectingQ
in your post. I wishDistanceMatrix
wasn't so stupid as to wrap theFalse
withAbs
.
– Jason B.
Nov 29 at 16:42
IfIntersectingQ
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 thatDistanceMatrix
has some considerable overhead.Outer
withIntersectingQ
is an order of magnitude faster for this example. But fo longer input lists,DistanceMatrix
withIntersection
seems to be faster. I am puzzled.
– Henrik Schumacher
Nov 29 at 16:46
add a comment |
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 *)
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 *)
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 noticingIntersectingQ
in your post. I wishDistanceMatrix
wasn't so stupid as to wrap theFalse
withAbs
.
– Jason B.
Nov 29 at 16:42
IfIntersectingQ
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 thatDistanceMatrix
has some considerable overhead.Outer
withIntersectingQ
is an order of magnitude faster for this example. But fo longer input lists,DistanceMatrix
withIntersection
seems to be faster. I am puzzled.
– Henrik Schumacher
Nov 29 at 16:46
add a comment |
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 noticingIntersectingQ
in your post. I wishDistanceMatrix
wasn't so stupid as to wrap theFalse
withAbs
.
– Jason B.
Nov 29 at 16:42
IfIntersectingQ
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 thatDistanceMatrix
has some considerable overhead.Outer
withIntersectingQ
is an order of magnitude faster for this example. But fo longer input lists,DistanceMatrix
withIntersection
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
add a comment |
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 SparseArray
s 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
add a comment |
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 SparseArray
s 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
add a comment |
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 SparseArray
s 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
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 SparseArray
s 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
edited Nov 29 at 17:04
answered Nov 29 at 16:37
Henrik Schumacher
47.3k466134
47.3k466134
add a comment |
add a comment |
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}
add a comment |
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}
add a comment |
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}
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}
edited Nov 30 at 8:56
answered Nov 29 at 18:47
kglr
175k9197402
175k9197402
add a comment |
add a comment |
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]
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
add a comment |
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]
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
add a comment |
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]
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]
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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