Function Repository Resource:

RemoveSubintervals

Source Notebook

Remove intervals that are wholly contained in other intervals

Contributed by: Carl Woll

ResourceFunction["RemoveSubintervals"][intervals]

removes an interval if it is wholly contained within another interval.

Details and Options

Only numeric pair lists or Interval objects are accepted.
When Interval objects with approximate machine-precision or arbitrary-precision endpoints are processed, the endpoints are not rounded further.

Examples

Basic Examples (2) 

A list of pairs representing intervals:

In[1]:=
list = {{1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 10}, {6, 10}, {7, 11}, {8,
     14}};

Remove pairs that are wholly contained in other intervals:

In[2]:=
ResourceFunction["RemoveSubintervals"][list]
Out[2]=

A list of Interval objects:

In[3]:=
list = {Interval[{1, 3}], Interval[{6, 7}], Interval[{2, 3}], Interval[{5, 8}]};

Remove intervals that are wholly contained within other intervals:

In[4]:=
ResourceFunction["RemoveSubintervals"][list]
Out[4]=

Scope (2) 

A large list of pairs:

In[5]:=
list = Table[
   RandomInteger[1000] {1, 1} + {0, RandomInteger[30]}, {10^5}];

The number of intervals left are removing all subintervals:

In[6]:=
ResourceFunction["RemoveSubintervals"][list] // Length // AbsoluteTiming
Out[6]=

A list of Interval objects with approximate real numbers:

In[7]:=
SeedRandom[1];
list = Interval /@ RandomReal[10, {5, 2}];

Remove subintervals:

In[8]:=
ResourceFunction["RemoveSubintervals"][list]
Out[8]=

The remaining Interval objects have not had their endpoints rounded further:

In[9]:=
list[[{1, 3}]] // FullForm
Out[9]=
In[10]:=
ResourceFunction["RemoveSubintervals"][list] // FullForm
Out[10]=

Possible Issues (1) 

Interval objects containing several intervals will be separated into distinct Interval objects:

In[11]:=
ResourceFunction[
 "RemoveSubintervals"][{Interval[{1, 3}, {5, 6}], Interval[{7, 8}]}]
Out[11]=

Publisher

Carl Woll

Version History

  • 1.0.0 – 04 November 2019

Author Notes

Uses Internal`ListMin, which is based on the BCL algorithm discussed here: https://dl.acm.org/citation.cfm?id=320196.

License Information