1
$\begingroup$

I am looking for suitable algorithm how to solve the following problem.

For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \emptyset$) on two ordered sets and assignment $\pi$ between elements of these two sets, where the following conditions must be fulfilled:

  1. $|A| = |B| = N$ where $N = \lfloor N_s/2 \rfloor$
  2. $s_k \in S$ where $k = 1,2, ...,N_s$
  3. $a_i \in A$ and $b_j \in B$ where $i,j = 1,2, ..., N$
  4. $\sum_{i=1}^{N}|a_{\pi(i)} - b_i| \to min$

In other words, I am looking for method how to find set of separated pairs $[a_{\pi(i)},b_i]$ assignments.

Example: $$S = [3.0, 2.1, 0.9, 2.9, 1.1], N_s = 5, N = 2$$ then $$A = [3.0, 0.9]$$ and $$B = [2.9, 1.1]$$ which produce following separate pairs:

$$[3.0, 2.9], [0.9, 1.1]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.

Improve this question
$\endgroup$
2
$\begingroup$

Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then:

  • If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more.

  • If $N_S$ is odd, enumerate over all possible items $s_i$ in $S$ and for each of them, compute the best partition of $S \setminus \{s_i\}$, which is an even-size set, using the previous case. Return the best partition among all $N_S$ cases.

The total cost of this procedure is $O(N_S \log N_S)$ when $N_S$ is even and $O(N_S^2 \log N_S)$ when $N_S$ is odd.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Nice! You can speed up the case of odd $N_S$ to run in $O(N_S \log N_S)$ time by a "prefix/suffix sum" type of trick: when $i$ is even, let $t_i$ denote the cost of the best partition of $s_1,\dots,s_i$; when $N_S-i+1$ is even, let $u_i$ denote the cost of the best partition of $s_i,\dots,s_{N_S}$. After sorting the $s_i$'s, you can compute the $t_i,u_i$'s in $O(N_S)$ time. Then you can compute the cost of the best partition of $S \setminus \{s_i\}$ in $O(1)$ time per $s_i$ from $t_{i-1}$ (or $t_{i-2}$) and $u_{i+1}$ (or $u_{i+2}$). $\endgroup$ – D.W.♦ Mar 29 '19 at 15:13
  • $\begingroup$ @D.W. Great! Could you provide simple pseudo code realization of prefix/suffix sum approach regarding this specific problem? I am not sure if I understand well your brief description. $\endgroup$ – michalkvasnicka Mar 29 '19 at 15:27
  • $\begingroup$ OK. Define $t_{2j} = t_{2j-2} + |s_{2j} - s_{2j-1}|$ and $u_{2j} = u_{2j+2} + |s_{2j+1} - s_{2j}|$. If $i$ is odd, the cost of the best partition of $S \setminus \{s_i\}$ is $t_{i-1} + u_{i+1}$. If $i$ is even, the cost of the best partition of $S \setminus \{s_i\}$ is $t_{i-2} + u_{i+2} + |s_{i+1}-s_{i-1}|$. You can compute all the $t$'s and $u$'s in linear time, then compute all of the costs of the best partition of $S \setminus \{s_i\}$ for all $i$ in linear time, then pick the one of lowest cost. @michalkvasnicka $\endgroup$ – D.W.♦ Mar 29 '19 at 16:35
  • $\begingroup$ @D.W. Sorry, but I still do not understand your indexing. Could you show me how looks like vectors $t_i$ and $u_i$, for $i=1,2,, ...,N_S$ in my simple example? $\endgroup$ – michalkvasnicka Apr 1 '19 at 10:57
  • $\begingroup$ @D.W. Your indexing is a bit confusing. For $i=1$ you have element $t_{i-2} = t_{-1}$. How is defined this element, for example? $\endgroup$ – michalkvasnicka Apr 1 '19 at 12:08

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.