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"]
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
$\endgroup$
int = List @@ (IntervalUnion @@ Interval /@ int) appears to fix this problem...
$\endgroup$
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 Developer`PartitionMap in place of BlockMap above. (thanks: @CarlWoll)
f1[{{1, 7}, {64, 80}}, 80].
$\endgroup$
BlockMap instead of Developer`PartitionMap.
$\endgroup$
BlockMap.
$\endgroup$
f1[{{1, 7}}, 80] still incorrectly returns {{1, 0}, {8, 80}}. The bug is only partially fixed.
$\endgroup$
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.