6
$\begingroup$

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.

|improve this question
$\endgroup$
8
$\begingroup$ 
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"]

enter image description here

|improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – SumNeuron Jun 26 '17 at 12:23
  • $\begingroup$ int = List @@ (IntervalUnion @@ Interval /@ int) appears to fix this problem... $\endgroup$ – SumNeuron Jun 26 '17 at 12:27
3
$\begingroup$ 
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)

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

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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