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$
2
  • $\begingroup$ what about {1,3} and {3,4}? Intersection gives {} $\endgroup$ Feb 8, 2015 at 5:26
  • $\begingroup$ @Algohi {1,3} and {3,4} should also be included in the result. $\endgroup$
    – Sungmin
    Feb 8, 2015 at 5:32

1 Answer 1

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$
5
  • $\begingroup$ I really like this as well as the 'separate' function on another recent question,+1 obviously:) $\endgroup$
    – ubpdqn
    Feb 8, 2015 at 7:59
  • 1
    $\begingroup$ @Mr. Wizard: Really cool solution! (+1)! $\endgroup$
    – mgamer
    Feb 8, 2015 at 8:55
  • $\begingroup$ @ubpdqn You might find the update of interest. $\endgroup$
    – Mr.Wizard
    Feb 8, 2015 at 10:06
  • $\begingroup$ @mgamer Thank you. You also may wish to look at the update. $\endgroup$
    – Mr.Wizard
    Feb 8, 2015 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, 2015 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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