# How to efficiently get the Complement of a Domain and several Intervals (IntervalComplement?)

Suppose you have a list of intervals (or tuples), such as:

intervals = {{3,7}, {17,43}, {64,70}};


And you wanted to know the intervals of all numbers not included above, e.g.:

myRange = 100;

numbersNotUed[myRange,intervales]

(*out: {{1,2},{8,16},{44,63},{71,100}}*)


What would be the most efficient way to approach this?

Mathematica currently supports IntervalIntersection but not IntervalComplement.

int = {{3, 7}, {17, 43}, {64, 70}};

com = Partition[#, 2]& @ {1, Sequence @@ Riffle[int[[All, 1]] - 1, int[[All, 2]] + 1], 100}


{{1, 2}, {8, 16}, {44, 63}, {71, 100}}

NumberLinePlot[{Interval @@ int, Interval @@ com}, PlotTheme -> "Detailed"]


• I marked this as the answer because it works... but it is susceptible to bugs. For example, try int = {{3, 7}, {7, 10}, {17, 43}, {64, 70}}; and then run com = Partition[#, 2] &@{1, Sequence @@ Riffle[int[[All, 1]] - 1, int[[All, 2]] + 1], 100}. You'll get {{1, 2}, {8, 6}, {11, 16}, {44, 63}, {71, 100}} which is peculiar – SumNeuron Jun 26 '17 at 12:23
• int = List @@ (IntervalUnion @@ Interval /@ int) appears to fix this problem... – SumNeuron Jun 26 '17 at 12:27
f1 = Partition[Flatten[{0, Select[Flatten@#, Function[x, x < #2]], #2 + 1}],
2, 2, {1, -1}, {}, ({1, -1} + {##}) /. {1, 0} -> Nothing &]&;

f1[{{3, 7}, {17, 43}, {64, 70}}, 80]


{{1, 2}, {8, 16}, {44, 63}, {71, 80}}

Also

f2 = BlockMap[({1, -1} + #) /. {1, 0} -> Nothing &,
Flatten[{0, Select[Flatten@#, Function[x, x < #2]], #2 + 1}], 2] &;
f2[{{3, 7}, {17, 43}, {64, 70}}, 80]


{{1, 2}, {8, 16}, {44, 63}, {71, 80}}

Note: In versions before 10.2 you can use DeveloperPartitionMap in place of BlockMap above. (thanks: @CarlWoll)

• Your implementation has a bug: please check f1[{{1, 7}, {64, 80}}, 80]. – Alexey Popkov Dec 20 '17 at 2:02
• Thank you @AlexeyPopkov. Fixed now. – kglr Dec 20 '17 at 2:31
• As of M10.2, you could use BlockMap instead of DeveloperPartitionMap. – Carl Woll Dec 20 '17 at 4:11
• Thank you @CarlWoll, I updated with a reference to BlockMap. – kglr Dec 20 '17 at 4:46
• f1[{{1, 7}}, 80] still incorrectly returns {{1, 0}, {8, 80}}. The bug is only partially fixed. – Alexey Popkov Dec 20 '17 at 7:19

Here is another implementation. It assumes that all the intervals lie in the specified range and intervals are sorted and aren't overlapping:

integerIntervalComplement[completeInterval : {start_, end_}, {subIntervals___}] :=
If[First[#2] - Last[#1] <= 1, Nothing, {Last[#1] + 1, First[#2] - 1}] & @@@
Partition[{{start - 1}, subIntervals, {end + 1}}, 2, 1];


Testing:

integerIntervalComplement[{1, 80}, {{3, 7}, {17, 43}, {64, 70}}]

{{1, 2}, {8, 16}, {44, 63}, {71, 80}}

integerIntervalComplement[{1, 80}, {{1, 7}, {64, 80}}]

{{8, 63}}

integerIntervalComplement[{1, 80}, {{2, 7}, {64, 79}}]

{{1, 1}, {8, 63}, {80, 80}}

integerIntervalComplement[{1, 80}, {}]

{{1, 80}}


If the intervals overlap, one can preprocess them first using Interval, for example:

List @@ Interval @@ {{30, 40}, {3, 7}, {8, 12}, {1, 10}}

{{1, 12}, {30, 40}}


This also removes the condition for subintervals to be sorted.