두 목록에있는 요소들 사이의 가장 작은 차이 합

Question

동일한 길이의 두 목록, ls1 및 ls2이 있다고 가정 해보십시오. 예를 들어, 우리는

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

있고 ls1의 각 요소에 대해, 우리는 방식으로, ls2 한 요소와 하나 개의 원소와 페어링 갖도록 전체 요소 사이에서 (절대) 차이 ls1에 있고 요소는 ls2입니다. 한 요소는 한 번만 일치 할 수 있습니다. 위의 예에서, 최적의 방법은 4이 최소 총 반환 ls2에 3와 ls1 및 I 프로그램을 필요

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

총 차이를 산출 ls2에 6와 ls1에 5이고 일치하는 이 두 목록에있는 요소 간의 차이. 목록의 길이는 임의적이며 목록의 요소 값도 마찬가지입니다 (그러나 모두 양의 정수입니다).

나는 현재 솔루션에 대한 순열을 사용하는 것이 해결책이라는 것을 알고 있지만, 최적의 시간과 공간의 복잡성을 가진 코드가 필요하다. 동적 프로그래밍의 개념에 대해 들어 봤지만, 제 경우에는 그것을 구현하는 방법을 모릅니다. 회신에 미리 감사드립니다.

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 

Answer 1

하나는 최적의 솔루션이 두 목록을 정렬하고 정렬 된 순서로 자신의 요소와 일치하는 것을 증명할 수 : 여기 런타임 또는 메모리 사용량이 효율적이지 내 현재의 브 루트 포스 코드를 사용하여 순열은입니다.

증거의 스케치 :

1. 있으라는 반전 될이, 즉 a가 b에 일치, c는 d 및 a < c, b > d에 일치합니다.

2. 우리는 이러한 요소를 교환 할 수 있습니다 : a->d, c->b. 지금 a < c, d < b. 이 작업은 대답을 늘릴 수 없음을 나타낼 수 있습니다 (a, b, c, d의 가능한 모든 상대 값 고려).

3. 따라서 항상 두 목록이 정렬되는 최적의 일치가 항상 있습니다.

가 여기에이 솔루션을 구현하는 효율적인 한 줄의 : @kraskevich가 지적했듯이

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

Answer 2

을 올바른 대답은 참으로 :

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 

우리가 알 수있는 바와 같이, 이차 약관^2 XN 및 YN^2는 동일하게 유지. 따라서 최소 결과를 얻으려면 음수 인 -2xn * yn을 최대화해야합니다.

이렇게하려면 한 목록의 가장 큰 값을 다른 목록의 가장 큰 값으로 간단히 곱한 다음 두 목록에서 두 번째로 큰 값에 대해 같은 작업을 수행하십시오 (Given 2 arrays, find the minimal sum of multiplication of indexes 참조). 따라서 목록을 모두 정렬하고 정렬 된 목록에서 동일한 색인의 요소를 곱함으로써 최소 차이 합을 얻습니다.