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]\ne \text{empty}$

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

• Step 4:
  $\{\begin{array}{lll}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{array}$
  $\Downarrow$
  $\{\begin{array}{lll}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{array}$
  $\Downarrow$

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

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

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

• Range 4:
  $\{\begin{array}{ll}v& \le x2-e\\ v& \ge x1-e\\ v& \ge x2-f\\ v& \ge c\\ v& \le d\end{array}$ $\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.