兩個列表中元素之間的最小差異總和

假設我們有兩個相同長度的列表ls1和ls2。例如，我們有兩個列表中元素之間的最小差異總和

ls1 = [4, 6] 
ls2 = [3, 5]

以及用於ls1每個元素，我們有一個元件帶有一個元件配對它在ls2，以這樣的方式，使得總的元件之間（絕對）差在ls1和ls2中的元素是最小的。一個元素只能匹配一次。在上面的例子中，最佳的方式是，以匹配4是ls1在ls23，和在ls15與6在ls2，其產生的

(4 - 3) + (6 - 5) = 2

我需要的程序的總差，返回這個最小總這兩個列表中的元素之間的差異。列表的長度是任意的，列表中元素的值也是任意的（但它們都是正整數）。

我目前知道，使用排列來強制解決方案是一個選項，但我需要的是具有最佳時間和空間複雜性的代碼。我聽說過動態編程的概念，但我不知道如何在我的情況下實現它。預先感謝回覆。

Ps。這是我目前使用蠻力代碼排列，這是不是在運行時或內存使用效率：

from itertools import permutations 

def minimum_total_difference(ls1, ls2): 
    length = len(ls1) 
    possibilities = list(permuations(ls1, length)) 
    out = 10**10 
    for possibility in possibilities: 
     out_ = 0 
     for _ in range(length): 
      diff = abs(possibility[_] - ls2[_]) 
      out += diff 
     if out_ < out: 
      out = out_ 
    return out

來源

2016-12-19 Jingjie YANG

這看起來像功課，你可以告訴你已經嘗試過什麼，如果是家庭作業，請注意，你的問題？ – TemporalWolf

另外，您想要每個列表的'n'索引或整個最小差異（即兩個列表中的任何元素）之間的最小差異？ –

真的你只是找不共享操作數 –

人能證明最優解是這兩個列表進行排序和匹配它們在排序順序元素。

證明的草圖：

要有反轉，即a匹配到b，c匹配到d和a < c, b > d。
我們可以「交換」這些元素：a->d, c->b。現在a < c, d < b。可以證明這個操作永遠不會增加答案（通過考慮所有可能的相對值a, b, c, d）
因此，總是有一個最佳匹配，其中兩個列表都被排序。

這裏是一個有效率的班輪實現這個解決方案：由於@kraskevich指出

sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys)))

來源

2016-12-19 20:08:56 kraskevich

，正確答案是確實：

sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys))

我已經想出了我自己的證明：
考慮兩個列表xs和ys，包含隨機順序的元素，x1,x2，... xn和y1,y2，...... yn。
由於我們試圖找出絕對差的最小和，我們可以使用平方根，而不是絕對值，它具有影響不大找到最小值。
因此的差之和就是：

(x1 - y1)^2 + (x2 - y2)^2 + ... + (xn - yn)^2 
=x1^2 - 2x1 * y1 + y1^2 + ... + xn^2 - 2xn * yn + yn^2

我們可以看到，不論是以何種方式，我們安排了兩個列表，二次項xn的^ 2^YN 2保持不變。所以，爲了獲得最小的結果，我們只需要最大化負項-2xn * yn。

爲了做到這一點，我們只需將一個列表中的最大值乘以另一個列表中的最大值，然後對兩個列表中的第二大值等進行相同操作（請參閱Given 2 arrays, find the minimal sum of multiplication of indexes）。因此，通過對排序列表中相同索引的列表和相乘元素進行排序，我們可以獲得最小差異總和。

來源

2016-12-23 18:53:19

兩個列表中元素之間的最小差異總和

回答

相關問題