Algortihm to find most similar elements in several groups

By | August 10, 2018

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.