3
$\begingroup$

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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.