It would be better to give an example first. Suppose I have a nested list of the form
list = {{ 1,2,3,6}, { 3,6,10,20}, { 4,7,11}, { 10,20}};
where each element of list
is a list of integers from a certain range (0, max)
.
The max
number is smaller enough than Length[list]
and thus I can expect there are many overlaps between elements.
Then I would like to find pairs of position {x,y}
such that Intersection[ list[[x]] , list[[y]] ] === {}
. In this example, I should find the pairs {1,4}
or {2,3}
but {1,2}
or {2,4}
should not be in the result.
Of course, the most naive approach is to make all possible subsets using Subsets[list,{2}]
then, check every pair. In my case, the length of list
is around 10^4 so this naive approach does not work in my environment.
It is guaranteed that the total number of such pairs are much smaller than all possible subsets n(n-1)/2
. Thus, I have a feeling that there should be a more efficient way to do so but could not find one so far.