Given 2 arrays, find the minimum sum of index multiplication

Question

Suppose I have two unsorted arrays of the same size, for example:

A = {1, 4, 3, 2} B = {5, 12, 1, 5} 

I would like to find the minimum sum of multiplication from every two cells - one from each array, that is, the sum A[i] * B[j] ( i is the index in A , j is the index in B ). what values ​​should be multiplied using values ​​from another array to get this minimum amount of products?

(I hope it is clear that after you have completed A[i]*A[j] , you will not be able to touch these cells again ...)

edit: for the example above, the minimum amount is: 1 * 4 + 3 * 5 + 5 * 2 + 1 * 12 = 31

Answer 1

To find the smallest summation, order one set in ascending order, the other go down, and then multiply along similar indices.

This is due to the fact that the smallest possible product for each pairing a[i] * b[j] (for a fixed a[i] due to the need to have a result for each element) is the smallest possible value of b[j] and vice versa.

This will also work with negatives, since the largest negative result is the smallest number and therefore the pairs with the most positive number from the result array. This continues even when both sets are completely negative, because the result of each multiplication becomes equivalent when both sets have negative values ​​of their values.

Answer 2

Aravol gives some intuition as to why optimal matching with reverse sorting is optimal, but with this view I find it useful to aggressively prove that it always works.

One way to prove this is to show that for any matching that has not yet been sorted in the opposite direction, changing this match a bit to make it “more like” sorting with reverse sorting never increases the total. If we show that this process

• can start with any match, but
• always ends when sorting with reverse sorting,

then we showed that matching with reverse sorting is no worse than any other match - this is the same as showing that it has the smallest possible sum. I want to emphasize that none of the following calculations is actually performed by any algorithm; for the purpose of proof, all we have to show is that they can be performed and that they will have the desired behavior, if so.

To do this, suppose that we are given an arbitrary match in the form of a set of pairs. As a first step, let them sort them in ascending order by their first element. (We can do this because the order in which the pairs are listed does not affect their sum.) Call the i-th pair after sorting (x [i], y [i]); by definition, after sorting, we have x [i] <= x [i + 1] for all i. Now, if the match is not already sorted by the return path, there should be a pair of adjacent y values ​​that violate the reverse sorting - that is, there must be some i such that y [i] y [g + 1]. Let us choose the first (lowest) value of i, for which this will happen, and see how a change in the total value of y [i] and y [i + 1] will affect the total. To do this, we can simply subtract the contribution of two old pairs and add the contribution of two new pairs: x [i] y [i + 1] + x [i + 1] y [i] - x [i] y [i] - x [ i + 1] y [i + 1] = x [i] (y [i + 1] - y [i]) + x [i + 1] (y [i] - y [i + 1]). Let d = y [i + 1] - y [i], this simplifies to x [i] d - x [i + 1] d = d (x [i] - x [i + 1]). We know x [i] - x [i + 1] <= 0, and because of the way we chose i, we also know d> 0, so their product should be & lt = 0. In other words, this swap is executed never increases the total.

But does it add us “closer” to sorting with reverse sorting and thus to completion? Yes, because repeating this procedure find-violation-then-swap behaves the same as inserting-sorting the first elements i + 1. Let us name the original value y [i + 1] z. After replacing y [i] and y [i + 1], the value of z has just returned one place in the list of pairs. If we start the process of searching for the first violation of reverse sorting, we can now find that it occurs at i-1 (that is, we find that y [i-1] <y [i]) - in this case, we can change y [i-1] to y [i], moving the z value back to another place. We can continue to do this until either z reaches y [1] or we find that the first position j is such that y [j] y [j + 1] also has the property that y [j -1]> = y [j + 1]: the latter means that the value of z has reached its final position, since we know that y [k]> = y [j-1] for all k <J-1. In any case, z will arrive at its final position after no more than I swaps, and the next violation detection run will find the position later than the original I - or determine that there is no such position (i.e. that the y values ​​are now sorted in reverse order).

In general, after no more than n ^ 2 find-violation-then-swap operations, the y values ​​will be sorted in reverse order, and the total amount will be no more than the original. Since we did not make any assumptions about the original collation that we gave, this result applies to any given collation, so we proved that collation with reverse sorting is at least as good as all of them. (Note that no aspect of this proof depends on the number of non-negative numbers, so this applies to arrays containing negative numbers.)

Answer 3

This theorem is called Reordering Unevenness.

Proof made:

The simplest evidence is nasty than one of @ j_random_hacker .

Suppose a is sorted in ascending order.

Since each cell never touches more than one, one choice corresponds to a permutation s , and the total sum f(s) = sum(a[i]*b[s(i)], i=1..n)

Since the number of permutations is finite, there is at least one minimum.

Name s1 one of these minima. therefore f(s1)<=f(s) for all s

We can transform it into a permutation s2 with the same sum f(s1)=f(s2)<=f(s) as if a[i] = a[i+1] then b[s2(i+1)] >= b[s2(i)] (1) simply by sorting in decreasing order the auxiliary array b [s1 (k)] .. b [s1 (k + n)] of b, where a[k] = a[k+1] = .. q[k+n]

So f(s2) also minimal. We show that b(s2[k]) decreases from the contrary.

Suppose that there exists i , for example b[s2(i)] < b[s2(i+1)] (2)

due to (1), a[i]!= a[i+1]

so a[i] < a[i+1] (3)

so b[s2(i)] - b[s2(i+1)] < 0 (4) as a consequence of (2)

so a[i] - a[i+1] < 0 (5) as a consequence of (3)

in this case

 a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)]-(a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)]) =a[i]*(b[s2(i)]-b[s2(i+1)])+a[i+1](b[s2(i+1)-b[s2(i)]) =(a[i]-a[i+1])(b[s2(i)]-b[s2(i+1)]) >=0 (because of product of two negative number because of (4) and (5) so a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] - (a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)])>0 so a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] > (a[i]*b[s2(i+1)]+a[i+1]*b[s2(i)]) (6) 

Set permutation s3 swapping i and i+1

 s3(n) = i+1 if n = i i if n = i+1 s2(n) a[i]*b[s2(i)]+a[i+1]*b[s2(i+1)] > (a[i]*b[s3(i)]+a[i+1]*b[s3(i+1)]) and a[n]*b[s2(n)]=s[n]*b[s3(n)] for n!= i and n!=i+1 so f(s2)>f(s3) 

So s3 is a better permutation than s2

There is a contradiction, therefore hypothesis (2) is false.

So, for all i b[s2(i)] < b[s2(i+1)] (2) false is used

So b[s2(i)] >= b[s2(i+1)] for all i

So s2 is such that b[s2(k)] is in decreasing order. Therefore, choosing a decrease for b gives an optimal result.

Using a similar proof, we can prove that the maximum product sum is specified by sorting a and b in ascending order.