1
$\begingroup$

I'd like to find an algorithm that can solve the following problem:

Consider 4 groups of numbers:

  • Group 1: [10, 100, 1000],
  • Group 2: [101, 15, 2000],
  • Group 3: [20, 1500, 100],
  • Group 4: [150, 3000, 13].

I need to select one number from each group so that the difference between the maximum and minimum of the four selected numbers would be the smallest among all possible combinations.

In this example, the numbers 10, 15, 20, 13 give the difference 10 and it is the smallest. The answer for the problem above is 10, 15, 20, 13.

I wonder if there is an algorithm that can solve this problem and also scales relatively well for a large number of groups and the number of entries in each group.

EDIT: @aurelian-tutuianu proposed an algorithm of complexity $O(nk\log k)$ that involves sorting each group. I wonder what would be the best algorithm if it's impossible to sort those groups. For instance, for groups

  • Group 1: [a1, a2, a3],
  • Group 2: [b1, b2, b3],
  • Group 3: [c1, c2, c3],
  • Group 4: [d1, d2, d3],

where I can find a pairwise similarity between all elements but cannot sort them.

$\endgroup$
  • 1
    $\begingroup$ does it have to be the smallest (implying an exact algorithm) or an approximate algorithm might suffice? $\endgroup$ – Anton Menshov Aug 11 '18 at 4:55
  • 1
    $\begingroup$ This is almost certainly an NP problem, i.e., there is no algorithm that scales well if you want to find the exact solution. $\endgroup$ – Wolfgang Bangerth Aug 12 '18 at 14:12
  • $\begingroup$ @AntonMenshov Yes, I would like to have an exact algorithm, but would consider any approximate solutions as well $\endgroup$ – aleksmath Aug 13 '18 at 14:29
  • $\begingroup$ @WolfgangBangerth If we consider only Group 1 and Group 2 and assume that those groups are sorted, then I can use a pairwise sequence alignment algorithm. However sorting might not be possible in some cases. I wonder if there is an alignment algorithm that doesn't require sorting. $\endgroup$ – aleksmath Aug 13 '18 at 14:36
0
$\begingroup$

Here is a solution. We assume the numbers from groups are sorted. We start with the following observation: any candidate solution will have the smallest number and the biggest number. To simplify we fix the smallest number and check which is the solution if that number is the smallest one. The algorithm follows these steps:

  1. Take the smallest number from the first numbers in each group. Remember groups are sorted. In your case, the smallest is 10
  2. Find the biggest difference between the smallest number and all first numbers from each group. This is guaranteed to be the optimal solution for the given smallest number.
  3. Keep the solution if it is the best seen for now. If it is the first solution found, keep it anyway for later comparison.
  4. Remove the smallest element from its group. If there are multiple groups then remove first elements from those groups too.
  5. If you have an empty group then you stop. The best solution seen so far is the optimal one. If your groups are not empty then continue with step 1.

If you put your groups in a priority queue or min heap at each step you spent $\log k$, where $k$ is the number of groups. Each solution verification takes k steps. For a total number of $n$ numbers from all groups, you will have $\mathcal O(nk \log k)$ running time.

Later edit: if at step 2 you find a difference bigger than best candidate so far you can avoid further computation because you know already you will not improve the solution

$\endgroup$
  • $\begingroup$ Thank you, @aurelian-tutuianu! That's a great answer. What would be complexity of the algorithm if I cannot sort the groups? (See my new edit of the question) $\endgroup$ – aleksmath Aug 15 '18 at 13:36
  • $\begingroup$ With no ordering is practically impossible to avoid enumeration of all combinations. I think if the distance is positive definite or it obey triangle rule we might cut some computation in backtracking, but the problem remains non polynomial $\endgroup$ – Aurelian Tutuianu Aug 18 '18 at 13:09

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.