6 replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/
source | link

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)(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}

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}

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}
5 refinements
source | link

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 @ LengthSubsets[Range @ listm, {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
{1817.969085104978, 8677}

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
  },
  Join @@
    ParallelTable[
      {i + 1, Min[n, i + block]} /. spec_ :>
        Pick[
         Subsets[Range @ Length @ list, {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
{18.969085, 86}

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}
4 added 20 characters in body
source | link

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
  },
  Join @@
    Table[ParallelTable[
      {i + 1, Min[n, i + block]} /. spec_ :>
        Pick[
         Subsets[Range @ Length @ list, {2}, spec],
         BitAnd @@@ Subsets[nums, {2}, spec],
         0
        ],
      {i, 0, n, block}
    ]
 ]

Perhaps this can be improved but at least it worksThe second parameter is the block size, default 10,000. Test:

max = 3000;

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

fn2[big]fn2[big, 50000] // Length // AbsoluteTiming
{4318.685499969085, 8486}

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
  },
  Join @@
    Table[
      {i + 1, Min[n, i + block]} /. spec_ :>
        Pick[
         Subsets[Range @ Length @ list, {2}, spec],
         BitAnd @@@ Subsets[nums, {2}, spec],
         0
        ],
      {i, 0, n, block}
    ]
 ]

Perhaps this can be improved but at least it works:

max = 3000;

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

fn2[big] // Length // AbsoluteTiming
{43.685499, 84}

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
  },
  Join @@
    ParallelTable[
      {i + 1, Min[n, i + block]} /. spec_ :>
        Pick[
         Subsets[Range @ Length @ list, {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
{18.969085, 86}
3 added 1053 characters in body
source | link
2 added 1053 characters in body
source | link
1
source | link