# Finding pairs where the intersection of them is empty set from a nested list

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.

• what about {1,3} and {3,4}? Intersection gives {} – Algohi Feb 8 '15 at 5:26
• @Algohi {1,3} and {3,4} should also be included in the result. – Sungmin Feb 8 '15 at 5:32

Given your input specification of integers from 0 through n a bit mask should work efficiently:

fn[list_] :=
Pick[
Subsets[Range @ Length @ list, {2}],
BitAnd @@@ Subsets[Tr /@ (2^list), {2}],
0
]


Test:

fn[list]

{{1, 3}, {1, 4}, {2, 3}, {3, 4}}


### Update

I misread your question as indicating that the maximum number is around 10^4, rather than you have 10^4 lists. As you note generating all subsets at once will not work well there. Instead we will need to operate in blocks(1)(2).

fn2[list_, block_: 10000] :=
With[{
nums = Tr /@ (2^list),
n = (# - 1) #/2 & @ Length @ list,
m = Length @ list
},
Join @@
ParallelTable[
{i + 1, Min[n, i + block]} /. spec_ :>
Pick[
Subsets[Range @ m, {2}, spec],
BitAnd @@@ Subsets[nums, {2}, spec],
0
],
{i, 0, n, block}
]
]


The second parameter is the block size, default 10,000. Test:

max = 3000;

big = DeleteDuplicates /@ RandomInteger[max, {10^4, 200}];

fn2[big, 50000] // Length // AbsoluteTiming

{17.104978, 77}

• I really like this as well as the 'separate' function on another recent question,+1 obviously:) – ubpdqn Feb 8 '15 at 7:59
• @Mr. Wizard: Really cool solution! (+1)! – mgamer Feb 8 '15 at 8:55
• @ubpdqn You might find the update of interest. – Mr.Wizard Feb 8 '15 at 10:06
• @mgamer Thank you. You also may wish to look at the update. – Mr.Wizard Feb 8 '15 at 10:06
• @Mr.Wizard yes have added it to my list for contemplation and hopefully use (with attribution of course) – ubpdqn Feb 8 '15 at 10:13