How to Get Combination Range

Background

There are three variables, name target,candidate and others,

• The range of target is $[a, b]$.
• The range of candidate is $[c, d]$.
• The range of others is $[e, f]$.

There is a relationshp: $target = candidate + others$
Now give the range of target $[x1, x2]$, to find the available combination for candidate and others.

Solution

• Step 1: Find the value of candidate $v \in [c, d]$.

• Step 2: $[e+v, f+v] \cap [x1, x2] \neq \empty$

• Step 3: $max(e+v, x1) \le min(f+v, x2)$

• Step 4:
  $\begin{cases} x1 &\le v+f &\text{if } x1 \ge e+v\text{ and } x2 \ge f+v\\ e+v &\le v+f &\text{if } x1 \le e+v\text{ and } x2 \ge f+v\\ x1 &\le x2 &\text{if } x1 \ge e+v\text{ and } x2 \le f+v\\ e+v &\le x2 &\text{if } x1 \le e+v\text{ and } x2 \le f+v \end{cases}$
  $\Downarrow$
  $\begin{cases} v &\ge x1-f &\text{if } x1 \ge e+v\text{ and } x2 \ge f+v\\ e &\le f &\text{if } x1 \le e+v\text{ and } x2 \ge f+v\\ x1 &\le x2 &\text{if } x1 \ge e+v\text{ and } x2 \le f+v\\ v &\le x2-e &\text{if } x1 \le e+v\text{ and } x2 \le f+v \end{cases}$
  $\Downarrow$

• Range 1:
  $\begin{cases} v &\ge x1-f \\ v &\le x1-e \\ v &\le x2-f \\ v &\ge c \\ v &\le d \end{cases}$ $\Rightarrow$ $v \in [max(x1-f, c), min(x1-e, x2-f, d)]$

• Range 2:
  $\begin{cases} v &\ge x1-e \\ v &\le x2-f\\ v &\ge c \\ v &\le d \end{cases}$ $\Rightarrow$ $v \in [max(x1-e, c), min(x2-f, d)]$

• Range 3:
  $\begin{cases} v &\ge x2-f \\ v &\le x1-e\\ v &\ge c \\ v &\le d \end{cases}$ $\Rightarrow$ $v \in [max(x2-f, c), min(x1-e, d)]$

• Range 4:
  $\begin{cases} v &\le x2-e \\ v &\ge x1-e \\ v &\ge x2-f\\ v &\ge c \\ v &\le d \end{cases}$ $\Rightarrow$ $v \in [max(x1-e, x2-f, c), min(x2-e, d)]$

• Step 5:

  1. select a value v in available ranges for candidate,
  2. update date target to [x1-v, x2-v]
  3. select one element from others as candidate and remove it from others
  • if others is not empty,
    4. update others as the sum of others elements (except new candidateelement)
    5. Go to Step 1.
  • else go to Step 6.

• Step 6:
  select a random value from the intersection of target and candidate.