6 replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/

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

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

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
2 added 1053 characters in body
1