8
$\begingroup$

How to calculate union, intersection and complement of integer intervals without actually generating all integers in the range and perform set-arithmetic (Union, Intersection, Complement) on them?

For simplicity, I define an integer interval as a list of disjoint {min, max} subintervals, each covering a consecutive range of integers. I expect the following output, each being the minimal representation of the interval:

union[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}] == {{-2, 7}, {10, 20}}

union[{{-2, 3}, {4, 7}, {15, 20}}] == {{-2, 7}, {15, 20}}

union[{}, {{}, {}}] == {}

intersection[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}] == {{15, 17}}

complement[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}] == {{-2, 3}, {18, 20}}

I have tried the followings (for union).

Interval-s are real-valued hence they do not merge:

IntervalUnion @@ (Interval /@ {{-2, 3}, {4, 7}, {15, 20}})

(* Interval[{-2, 3}, {4, 7}, {15, 20}] *)

Inequalities representing neighbouring intervals are not always simplified:

FullSimplify[Or @@ (First@# <= x <= Last@# & /@ {{-2, 3}, {4, 7}, {15, 20}}), x \[Element] Integers]

(* -2 <= x <= 3 || 4 <= x <= 7 || 15 <= x <= 20 *)

Solve returns elementary solutions (regardless of the region represented as Interval or ImplicitRegion:

r = RegionUnion @@ (ImplicitRegion[First@# <= x <= Last@# && x \[Element] Integers, x] & /@ 
    {{-2, 3}, {4, 7}, {15, 20}});
x /. Solve[x \[Element] r, x, Integers]

(* {{-2}, {-1}, {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {15}, {16}, {17}, {18}, {19}, {20}} *)

Of course one can work around any of these shortcomings by structural manipulation of the results, but I am interested in whether there is a polished domestic (undocumented) solution or not.

$\endgroup$
2
  • 1
    $\begingroup$ Maybe you should look at implementing an Interval Tree $\endgroup$
    – flinty
    Commented Jan 6, 2023 at 16:53
  • 1
    $\begingroup$ For your Inequality example, applying LogicalExpand before FullSimplify seems to help. $\endgroup$
    – Ben Izd
    Commented Jan 6, 2023 at 17:05

3 Answers 3

2
$\begingroup$

Solution The OP says this does not answer the question.

You can transform your list of {min, max} into ImplicitRegion explicitly specifying Integer domain.

List to region

ClearAll[intInterval];
intInterval[{a_Integer,b_Integer}]:= ImplicitRegion[ And[ a <= x <= b, Element[x,Integers] ], x]
intInterval[{il___List}] := RegionUnion@@ Map[intInterval, {il}]

Tests

Now we can run the checks using RegionEqual.

Union

Using RegionUnion

RegionEqual[
    RegionUnion[
        intInterval@{{-2, 3}, {15, 20}}, 
        intInterval@{{4, 7}, {10, 17}}
    ] ,
        intInterval@{{-2, 7}, {10, 20}}
]
(* True *)

Intersection

Using RegionIntersection

RegionEqual[
    RegionIntersection[
        intInterval@{{-2, 3}, {15, 20}},
        intInterval@{{4, 7}, {10, 17}}
    ],
    intInterval@{{15, 17}}
]
(* True *)

Complement

Using RegionDifference

RegionEqual[
    RegionDifference [
        intInterval@{{-2, 3}, {15, 20}}, 
        intInterval@{{4, 7}, {10, 17}}
    ],
    intInterval@{{-2, 3}, {18, 20}}
]
(* True *)

Region simplify

ClearAll[regionSimplify];
regionSimplify[ir_ImplicitRegion]:=ImplicitRegion[
    And[
        Element[ir[[2,1]],Integers],
        FullSimplify[
            ir[[1,2]]
            , Element[ir[[2,1]],Integers]
            , ComplexityFunction-> Function[expr, LeafCount[expr]-500*Count[expr,LessEqual]+50*Count[expr,Or]]
        ]
    ]
    ,{x}
]

Region to list

region2list[ir_ImplicitRegion]:=ReplaceAll[
    regionSimplify[ir][[1]]
    , {Or->List,Inequality[a_,LessEqual,x,LessEqual,b_]->{a,b}, x\[Element]Integers->True }
]
$\endgroup$
6
  • 1
    $\begingroup$ This is nice, but it circumvents the problem. What I need is not the ability to compare the resulting interval to any other interval, but to have a list of disjoint subintervals like {{min1, max1}, {min2, max2}, ...}. Implicit regions do not simplify the inequalities. $\endgroup$ Commented Jan 6, 2023 at 16:00
  • $\begingroup$ Yeah, but compare FullSimplify[x \[Element] Integers && (-2 <= x <= 3 || 4 <= x <= 7 || 10 <= x <= 17 || 15 <= x <= 20), x \[Element] Integers] with FullSimplify[x \[Element] Integers && (-2 <= x <= 3 || 4 <= x <= 7 || 15 <= x <= 20), x \[Element] Integers]. $\endgroup$ Commented Jan 6, 2023 at 16:47
  • $\begingroup$ I want to maintain a minimal representation of the interval. Either {{-2, 7}} or -2 <= x <= 7, it does not matter, but certainly not -2 <= x <= 3 || 4 <= x <= 7. However, simplification does not always yield the minimal form as my above example demonstrates (I've added this to my post). $\endgroup$ Commented Jan 6, 2023 at 17:00
  • $\begingroup$ @IstvánZachar check the edit and the definition of regionSimplify and region2list. $\endgroup$
    – rhermans
    Commented Jan 6, 2023 at 17:17
  • $\begingroup$ I have the feeling, that relying on Simplify and LogicalExpand (perhaps Reduce), one can get rid of the Region-overhead entirely, at least for union. However, it is still very messy, as any resulting inequality is not standardized and can be of many forms (Less, LessEqual, Greater, GreaterEqual, Inequality, etc., especially if Infinity (- and +) is allowed), which all require structural identification to convert to boundaries. $\endgroup$ Commented Jan 7, 2023 at 15:18
1
$\begingroup$

I have implemented some rudimentary functions to do this.

Integer intervals are represented as defined above: a list of disjoint, ordered boundary pairs of integers (or +/- infinity). Each function assumes that the input is already numerically sorted, each subinterval is numerically ordered and subintervals are not overlapping.

These functions are far from being optimal, but already orders of magnitude faster than relying on Region arithmetic or Simplify-ing inequalities. Please feel free to suggest improvements.

ClearAll[intervalUnion, intervalIntersection, intervalDifference];

$pos = _Integer | ∞ | -∞;
$int = {$pos, $pos};

intervalUnion[set:$int, add_] := intervalUnion[{set}, add];
intervalUnion[{}, add:$int] := {add};
intervalUnion[set:{__List}, {}] := set;
intervalUnion[set:{__List}, {min:$pos, max:$pos}] := Which[
   max < set[[1, 1]] - 1, Prepend[set, {min, max}],
   min > set[[-1, -1]] + 1, Append[set, {min, max}],
   True, Module[{n = Length@set, i = 1, minQ = True, maxQ = True, from, to},
    to = n;
    While[(minQ || maxQ) && i <= n,
     If[minQ && set[[i, 2]] + 1 >= min, minQ = False; from = i];
     If[maxQ && set[[i, 1]] > max + 1, maxQ = False; to = i - 1];
     i++];
    Insert[Drop[set, {from, to}], {Min[min, set[[from, 1]]], 
      Max[max, set[[to, 2]]]}, from]]];
intervalUnion[{}] := {};
intervalUnion[set:{__List}] := Fold[intervalUnion, set];
intervalUnion[set:{___List}, add:{___List}] := intervalUnion@Join[set, add];


intervalIntersection[_List, {}] := {};
intervalIntersection[{}, _List] := {};
intervalIntersection[{amin:$pos, amax:$pos}, {bmin:$pos, bmax:$pos}] := 
  If[amax < bmin || amin > bmax, {}, {Max[amin, bmin], Min[amax, bmax]}];
intervalIntersection[a:$int, b:{$int..}] := intervalIntersection[{a}, b];
intervalIntersection[a:{$int..}, b:$int] := intervalIntersection[a, {b}];
intervalIntersection[a:{$int..}, b:{$int..}] := 
  DeleteCases[Flatten[Outer[intervalIntersection, a, b, 1], 1], {}];


intervalDifference[{}, _List] := {};
intervalDifference[all:$int, set:$int] := intervalDifference[all, {set}];
intervalDifference[all:$int, {} | {{}}] := {all};
intervalDifference[all:$int, set:{$int..}] := intervalIntersection[
   all, (# + {1, -1} & /@ Partition[Flatten@set, 2, 2, {-1, 1}, {∞, -∞}])];
intervalDifference[all:{$int...}, set:{$int...}] := 
   Flatten[intervalDifference[#, set] & /@ all, 1];

Testing:

intervalUnion[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {{-2, 7}, {10, 20}} *)

intervalUnion[{{-2, 3}, {4, 7}, {15, 20}}]
(*  {{-2, 7}, {15, 20}} *)

intervalUnion[{}, {{}, {}}]
(* {} *)

intervalIntersection[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {{15, 17}} *)

intervalDifference[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {{-2, 3}, {18, 20}} *)
$\endgroup$
1
$\begingroup$

You could represent the interval $[a,b]\cap\mathbb{Z}$ as $[a,b+1[$, i.e. you take the interval over the reals with the upper bound extended to just below the next integer. This has the advantage that intervals that "touch" over the integers also "touch" over the reals, meaning everything is automatically simplified.

While Interval doesn't support open intervals, you can use inequalities and use Reduce to do all the heavy lifting. Concretely, implementing your examples:

intervalConstr[x_][{ints : {_Integer, _Integer} ...}] :=
 Or @@ (# <= x < #2 + 1 & @@@ {ints})
intervalConstr[x_][ints : {_Integer, _Integer} ...] :=
 Or @@ (# <= x < #2 + 1 & @@@ {ints})

toIntervals[x_][a_ <= x_ < b_] :=
 {a, b - 1}
toIntervals[x_][segs_Or] :=
 List @@ (toIntervals[x, #] & /@ segs)
toIntervals[_][False] :=
 {}

union[ints__] :=
 toIntervals[x]@Reduce[Or @@ intervalConstr[x] /@ {ints}]
intersection[ints__] :=
 toIntervals[x]@Reduce[And @@ intervalConstr[x] /@ {ints}]
complement[inta_, ints__] :=
 toIntervals[x]@
  Reduce[intervalConstr[x]@inta && And @@ Not@*intervalConstr[x] /@ {ints}]

union[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {{-2, 7}, {10, 20}} *)

union[{}, {}]
(* {} *)

intersection[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {15, 17} *)

complement[{{-2, 3}, {15, 20}}, {{4, 7}, {10, 17}}]
(* {{-2, 3}, {18, 20}} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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