Getting the lowest possible sum from numbers' difference

Question

I have to find the lowest possible sum from numbers' difference.

Let's say I have 4 numbers. 1515, 1520, 1500 and 1535. The lowest sum of difference is 30, because 1535 - 1520 = 15 && 1515 - 1500 = 15 and 15 + 15 = 30. If I would do like this: 1520 - 1515 = 5 && 1535 - 1500 = 35 it would be 40 in sum.

Hope you got it, if not, ask me.

Any ideas how to program this? I just found this online, tried to translate from my language to English. It sounds interesting. I can't do bruteforce, because it would take ages to compile. I don't need code, just ideas how to program or little fragment of code.

Thanks.

Edit: I didn't post everything... One more edition:

I have let's say 8 possible numbers. But I have to take only 6 of them to make the smallest sum. For instance, numbers 1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731, the smallest sum will be 48, but here I have to take only 6 numbers from 8.

Answer 1

Taking the edit into account:

Start by sorting the list. Then use a dynamic programming solution, with state i, n representing the minimum sum of n differences when considering only the first i numbers in the sequence. Initial states: dp[*][0] = 0, everything else = infinity. Use two loops: outer loop looping through i from 1 to N, inner loop looping through n from 0 to R (3 in your example case in your edit - this uses 3 pairs of numbers which means 6 individual numbers). Your recurrence relation is dp[i][n] = min(dp[i-1][n], dp[i-2][n-1] + seq[i] - seq[i-1]).

You have to be aware of handling boundary cases which I've ignored, but the general idea should work and will run in O(N log N + NR) and use O(NR) space.

Answer 2

The solution by marcog is a correct, non-recursive, polynomial-time solution to the problem — it's a pretty standard DP problem — but, just for completeness, here's a proof that it works, and actual code for the problem. [@marcog: Feel free to copy any part of this answer into your own if you wish; I'll then delete this.]

Proof

Let the list be x₁, …, x_N. Assume wlog that the list is sorted. We're trying to find K (disjoint) pairs of elements from the list, such that the sum of their differences is minimised.

Claim: An optimal solution always consists of the differences of consecutive elements.
Proof: Suppose you fix the subset of elements whose differences are taken. Then by the proof given by Jonas Kölker, the optimal solution for just this subset consists of differences of consecutive elements from the list. Now suppose there is a solution corresponding to a subset that does not comprise pairs of consecutive elements, i.e. the solution involves a difference x_j-x_i where j>i+1. Then, we can replace x_j with x_i+1 to get a smaller difference, since
x_i ≤ x_i+1 ≤ x_j ⇒ x_i+1-x_i ≤ x_j-x_i.
(Needless to say, if x_i+1=x_j, then taking x_i+1 is indistinguishable from taking x_j.) This proves the claim.

The rest is just routine dynamic programming stuff: the optimal solution using k pairs from the first n elements either doesn't use the nth element at all (in which case it's just the optimal solution using k pairs from the first n-1), or it uses the nth element in which case it's the difference x_n-x_n-1 plus the optimal solution using k-1 pairs from the first n-2.

The whole program runs in time O(N log N + NK), as marcog says. (Sorting + DP.)

Code

Here's a complete program. I was lazy with initializing arrays and wrote Python code using dicts; this is a small log(N) factor over using actual arrays.

'''
The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers
'''
import sys
def ints(): return [int(s) for s in sys.stdin.readline().split()]

N, K = ints()
num = sorted(ints())

best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n
def b(k,n):
    if best.has_key((k,n)): return best[(k,n)]
    if k==0: return 0
    return float('inf')

for n in range(1,N):
    for k in range(1,K+1):
        best[(k,n)] = min([b(k,n-1),                      #Not using num[n]
                           b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n]

print best[(K,N-1)]

Test it:

Input
4 2
1515 1520 1500 1535
Output
30

Input
8 3
1731 1572 2041 1561 1682 1572 1609 1731
Output
48

Answer 3

I assume the general problem is this: given a list of 2n integers, output a list of n pairs, such that the sum of |x - y| over all pairs (x, y) is as small as possible.

In that case, the idea would be:

• sort the numbers
• emit (numbers[2k], numbers[2k+1]) for k = 0, ..., n - 1.

This works. Proof:

Suppose you have x_1 < x_2 < x_3 < x_4 (possibly with other values between them) and output (x_1, x_3) and (x_2, x_4). Then

|x_4 - x_2| + |x_3 - x_1| = |x_4 - x_3| + |x_3 - x_2| + |x_3 - x_2| + |x_2 - x_1| >= |x_4 - x_3| + |x_2 - x_1|.

In other words, it's always better to output (x_1, x_2) and (x_3, x_4) because you don't redundantly cover the space between x_2 and x_3 twice. By induction, the smallest number of the 2n must be paired with the second smallest number; by induction on the rest of the list, pairing up smallest neighbours is always optimal, so the algorithm sketch I proposed is correct.

Answer 4

Order the list, then do the difference calculation.

EDIT: hi @hey

You can solve the problem using dynamic programming.

Say you have a list L of N integers, you must form k pairs (with 2*k <= N)

Build a function that finds the smallest difference within a list (if the list is sorted, it will be faster ;) call it smallest(list l)

Build another one that finds the same for two pairs (can be tricky, but doable) and call it smallest2(list l)

Let's define best(int i, list l) the function that gives you the best result for i pairs within the list l

The algorithm goes as follows:

1. best(1, L) = smallest(L)
2. best(2, L) = smallest2(L)
3. for i from 1 to k:

loop

compute min ( 
    stored_best(i-2) - smallest2( stored_remainder(i-2) ),
    stored_best(i-1) - smallest( stored_remainder(i-1) 
) and store as best(i)
store the remainder as well for the chosen solution

Now, the problem is once you have chosen a pair, the two ints that form the boundaries are reserved and can't be used to form a better solution. But by looking two levels back you can guaranty you have allowed switching candidates.

(The switching work is done by smallest2)

Answer 5

Step 1: Calculate pair differences

I think it is fairly obvious that the right approach is to sort the numbers and then take differences between each adjacent pair of numbers. These differences are the "candidate" differences contributing to the minimal difference sum. Using the numbers from your example would lead to:

Number Diff
====== ====
1561
        11
1572
         0
1572
        37
1609
        73
1682
        49
1731
         0
1731
       310
2041

Save the differences into an array or table or some other data structure where you can maintain the differences and the two numbers that contributed to each difference. Call this the DiffTable. It should look something like:

Index Diff Number1 Number2
===== ==== ======= =======
  1     11    1561    1572
  2      0    1572    1572
  3     37    1572    1609
  4     73    1609    1682
  5     49    1682    1731
  6      0    1731    1731
  7    310    1731    2041

Step 2: Choose minimal Differences

If all numbers had to be chosen, we could have stopped at step 1 by choosing the number pair for odd numbered indices: 1, 3, 5, 7. This is the correct answer. However, the problem states that a subset of pairs are chosen and this complicates the problem quite a bit. In your example 3 differences (6 numbers = 3 pairs = 3 differences) need to be chosen such that:

• The sum of the differences is minimal
• The numbers participating in any chosen difference are removed from the list.

The second point means that if we chose Diff 11 (Index = 1 above), the numbers 1561 and 1572 are removed from the list, and consequently, the next Diff of 0 at index 2 cannot be used because only 1 instance of 1572 is left. Whenever a Diff is chosen the adjacent Diff values are removed. This is why there is only one way to choose 4 pairs of numbers from a list containing eight numbers.

About the only method I can think of to minimize the sum of the Diff above is to generate and test.

The following pseudo code outlines a process to generate all 'legal' sets of index values for a DiffTable of arbitrary size where an arbitrary number of number pairs are chosen. One (or more) of the generated index sets will contain the indices into the DiffTable yielding a minimum Diff sum.

/* Global Variables */
M = 7    /* Number of candidate pair differences in DiffTable */
N = 3    /* Number of indices in each candidate pair set (3 pairs of numbers) */
AllSets = [] /* Set of candidate index sets (set of sets) */

call GenIdxSet(1, []) /* Call generator with seed values */

/* AllSets now contains candidate index sets to perform min sum tests on */

end

procedure: GenIdxSet(i, IdxSet)
  /* Generate all the valid index values for current level */
  /* and subsequent levels until a complete index set is generated */
  do while i <= M
     if CountMembers(IdxSet) = N - 1 then  /* Set is complete */
        AllSets = AppendToSet(AllSets, AppendToSet(IdxSet, i))
     else                                  /* Add another index */
       call GenIdxSet(i + 2, AppendToSet(IdxSet, i))
     i = i + 1
     end
return

Function CountMembers returns the number of members in the given set, function AppendToSet returns a new set where the arguments are appended into a single ordered set. For example AppendToSet([a, b, c], d) returns the set: [a, b, c, d].

For the given parameters, M = 7 and N = 3, AllSets becomes:

[[1 3 5]
 [1 3 6]  <= Diffs = (11 + 37 + 0) = 48
 [1 3 7]
 [1 4 6]
 [1 4 7]
 [1 5 7]
 [2 4 6]
 [2 4 7]
 [2 5 7]
 [3 5 7]]

Calculate the sums using each set of indices, the one that is minimum identifies the required number pairs in DiffTable. Above I show that the second set of indices gives the minimum you are looking for.

This is a simple brute force technique and it does not scale very well. If you had a list of 50 number pairs and wanted to choose the 5 pairs, AllSets would contain 1,221,759 sets of number pairs to test.

Answer 6

I know you said you did not need code but it is the best way for me to describe a set based solution. The solution runs under SQL Server 2008. Included in the code is the data for the two examples you give. The sql solution could be done with a single self joining table but I find it easier to explain when there are multiple tables.

    --table 1 holds the values

declare @Table1 table (T1_Val int)
Insert @Table1 
--this data is test 1
--Select (1515) Union ALL
--Select (1520) Union ALL
--Select (1500) Union ALL
--Select (1535) 

--this data is test 2
Select (1731) Union ALL
Select (1572) Union ALL
Select (2041) Union ALL
Select (1561) Union ALL
Select (1682) Union ALL
Select (1572) Union ALL
Select (1609) Union ALL
Select (1731) 
--Select * from @Table1

--table 2 holds the sorted numbered list
Declare @Table2 table (T2_id int identity(1,1), T1_Val int)
Insert @Table2 Select T1_Val from @Table1 order by T1_Val

--table 3 will hold the sorted pairs
Declare @Table3 table (T3_id int identity(1,1), T21_id int, T21_Val int, T22_id int, T22_val int)
Insert @Table3
Select T2_1.T2_id, T2_1.T1_Val,T2_2.T2_id, T2_2.T1_Val from @Table2 AS T2_1
LEFT Outer join @Table2 AS T2_2 on T2_1.T2_id = T2_2.T2_id +1

--select * from @Table3
--remove odd numbered rows
delete from @Table3 where T3_id % 2 > 0 

--select * from @Table3
--show the diff values
--select *, ABS(T21_Val - T22_val) from @Table3
--show the diff values in order
--select *, ABS(T21_Val - T22_val) from @Table3 order by ABS(T21_Val - T22_val)
--display the two lowest
select TOP 2 CAST(T22_val as varchar(24)) + ' and ' + CAST(T21_val as varchar(24)) as 'The minimum difference pairs are'
, ABS(T21_Val - T22_val) as 'Difference'
from @Table3
ORDER by ABS(T21_Val - T22_val) 

Answer 7

I think @marcog's approach can be simplified further.

Take the basic approach that @jonas-kolker proved for finding the smallest differences. Take the resulting list and sort it. Take the R smallest entries from this list and use them as your differences. Proving that this is the smallest sum is trivial.

@marcog's approach is effectively O(N^2) because R == N is a legit option. This approach should be (2*(N log N))+N aka O(N log N).

This requires a small data structure to hold a difference and the values it was derived from. But, that is constant per entry. Thus, space is O(N).

Answer 8

I would go with answer of marcog, you can sort using any of the sorting algoriothms. But there is little thing to analyze now.

If you have to choose R numbers out N numbers so that the sum of their differences is minimum then the numbers be chosen in a sequence without missing any numbers in between.

Hence after sorting the array you should run an outer loop from 0 to N-R and an inner loop from 0 to R-1 times to calculate the sum of differnces.

If needed, you should try with some examples.

Answer 9

I've taken an approach which uses a recursive algorithm, but it does take some of what other people have contributed.

First of all we sort the numbers:

[1561,1572,1572,1609,1682,1731,1731,2041]

Then we compute the differences, keeping track of which the indices of the numbers that contributed to each difference:

[(11,(0,1)),(0,(1,2)),(37,(2,3)),(73,(3,4)),(49,(4,5)),(0,(5,6)),(310,(6,7))]

So we got 11 by getting the difference between number at index 0 and number at index 1, 37 from the numbers at indices 2 & 3.

I then sorted this list, so it tells me which pairs give me the smallest difference:

[(0,(1,2)),(0,(5,6)),(11,(0,1)),(37,(2,3)),(49,(4,5)),(73,(3,4)),(310,(6,7))]

What we can see here is that, given that we want to select n numbers, a naive solution might be to select the first n / 2 items of this list. The trouble is, in this list the third item shares an index with the first, so we'd only actually get 5 numbers, not 6. In this case you need to select the fourth pair as well to get a set of 6 numbers.

From here, I came up with this algorithm. Throughout, there is a set of accepted indices which starts empty, and there's a number of numbers left to select n:

1. If n is 0, we're done.
2. if n is 1, and the first item will provide just 1 index which isn't in our set, we taken the first item, and we're done.
3. if n is 2 or more, and the first item will provide 2 indices which aren't in our set, we taken the first item, and we recurse (e.g. goto 1). This time looking for n - 2 numbers that make the smallest difference in the remainder of the list.

This is the basic routine, but life isn't that simple. There are cases we haven't covered yet, but make sure you get the idea before you move on.

Actually step 3 is wrong (found that just before I posted this :-/), as it may be unnecessary to include an early difference to cover indices which are covered by later, essential differences. The first example ([1515, 1520, 1500, 1535]) falls foul of this. Because of this I've thrown it away in the section below, and expanded step 4 to deal with it.

So, now we get to look at the special cases:

1. ** as above **
2. ** as above **
3. If n is 1, but the first item will provide two indices, we can't select it. We have to throw that item away and recurse. This time we're still looking for n indices, and there have been no changes to our accepted set.
4. If n is 2 or more, we have a choice. Either we can a) choose this item, and recurse looking for n - (1 or 2) indices, or b) skip this item, and recurse looking for n indices.

4 is where it gets tricky, and where this routine turns into a search rather than just a sorting exercise. How can we decide which branch (a or b) to take? Well, we're recursive, so let's call both, and see which one is better. How will we judge them?

• We'll want to take whichever branch produces the lowest sum.
• ...but only if it will use up the right number of indices.

So step 4 becomes something like this (pseudocode):

x       = numberOfIndicesProvidedBy(currentDifference)
branchA = findSmallestDifference (n-x, remainingDifferences) // recurse looking for **n-(1 or 2)**
branchB = findSmallestDifference (n  , remainingDifferences) // recurse looking for **n** 
sumA    = currentDifference + sumOf(branchA)
sumB    =                     sumOf(branchB) 

validA  = indicesAddedBy(branchA) == n
validB  = indicesAddedBy(branchB) == n

if not validA && not validB then return an empty branch

if validA && not validB then return branchA
if validB && not validA then return branchB

// Here, both must be valid.
if sumA <= sumB then return branchA else return branchB

I coded this up in Haskell (because I'm trying to get good at it). I'm not sure about posting the whole thing, because it might be more confusing than useful, but here's the main part:

findSmallestDifference = findSmallestDifference' Set.empty

findSmallestDifference' _     _ [] = []
findSmallestDifference' taken n (d:ds)
    | n == 0                = []    -- Case 1
    | n == 1 && provides1 d = [d]   -- Case 2
    | n == 1 && provides2 d = findSmallestDifference' taken n ds -- Case 3
    | provides0 d           = findSmallestDifference' taken n ds -- Case 3a (See Edit)
    | validA && not validB             = branchA -- Case 4
    | validB && not validA             = branchB -- Case 4
    | validA && validB && sumA <= sumB = branchA -- Case 4
    | validA && validB && sumB <= sumA = branchB -- Case 4
    | otherwise             = []                 -- Case 4
        where branchA = d : findSmallestDifference' (newTaken d) (n - (provides taken d)) ds
              branchB = findSmallestDifference' taken n ds
              sumA    = sumDifferences branchA
              sumB    = sumDifferences branchB
              validA  = n == (indicesTaken branchA)
              validB  = n == (indicesTaken branchA)
              newTaken x = insertIndices x taken 

Hopefully you can see all the cases there. That code(-ish), plus some wrapper produces this:

*Main> findLeastDiff 6 [1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731]
Smallest Difference found is 48
      1572 -   1572 =      0
      1731 -   1731 =      0
      1572 -   1561 =     11
      1609 -   1572 =     37
*Main> findLeastDiff 4 [1515, 1520, 1500,1535]
Smallest Difference found is 30
      1515 -   1500 =     15
      1535 -   1520 =     15

This has become long, but I've tried to be explicit. Hopefully it was worth while.

---

Edit : There is a case 3a that can be added to avoid some unnecessary work. If the current difference provides no additional indices, it can be skipped. This is taken care of in step 4 above, but there's no point in evaluating both halves of the tree for no gain. I've added this to the Haskell.

Answer 10

Something like

1. Sort List
2. Find Duplicates
3. Make the duplicates a pair
4. remove duplicates from list
5. break rest of list into pairs
6. calculate differences of each pair
7. take lowest amounts

In your example you have 8 number and need the best 3 pairs. First sort the list which gives you

1561, 1572, 1572, 1609, 1682, 1731, 1731, 2041

If you have duplicates make them a pair and remove them from the list so you have

[1572, 1572] = 0
[1731, 1731] = 0
L = { 1561, 1609, 1682, 2041 }

Break the remaining list into pairs, giving you the 4 following pairs

[1572, 1572] = 0
[1731, 1731] = 0
[1561, 1609] = 48
[1682, 2041] = 359

Then drop the amount of numbers you need to.

This gives you the following 3 pairs with the lowest pairs

[1572, 1572] = 0
[1731, 1731] = 0
[1561, 1609] = 48

So

0 + 0 + 48 = 48