两个列表之间的值的差异

Question

我正在解决一个练习问题，并希望使用递归找到两个列表之间的最小差异。例如，如果我有一个值为[79, 85, 10]的列表X和一个值为[78, 80, 87, 12]的列表Y，则这两个列表之间的差异将为4。

我尝试遍历这两个列表，但无法找到如何仅查找差异最小的总和，而不仅返回配对结果。

我希望这个函数能够返回滑雪者和滑雪板的配对，但不返回代表给定两个列表之间最小差异的总和。

- user7339685

---

什么是“滑雪者/滑雪者身高问题”，您如何计算这两个列表之间的最小差异为4？ - jarmod

抱歉造成混乱，我已经编辑了问题并提供了更多的信息！ - user7339685

以前从未听说过这个问题，看起来很有趣。 - cglacet

Answer 1

一种解决方案是使用NumPy在skis列表中找到最接近的值（NumPy函数来自于在NumPy数组中查找最接近的值）。然后遍历滑雪者并找到最接近的尺码。记得从列表中删除该尺码。

import numpy as np

def find_nearest(array, value):
    array = np.asarray(array)
    idx = (np.abs(array-value)).argmin()
    return array[idx]

def pair(x, y):
    skier_skis = []
    skis_left = list(y)
    for skier in x:
        skier_skis.append((skier, find_nearest(skis_left, skier)))
        skis_left.remove(skier_skis[-1][1])
    return skier_skis

skiers = [6, 11, 13]
skis = [5, 7, 9, 14]
pair(skiers, skis)

返回 [(6,5),(11,9),(13,14)]。

如果您的目标只是返回最小差异，则需要遍历 skier_skis 列表并求和其差值。

编辑：正如 @Rivers Shall 指出的那样，这种方法可能并不总是返回最优解。

- minterm

---

谢谢你提供的解决方案！我尝试不使用Python内置函数，而是使用简单的递归。但我很感激你的帮助！ - user7339685

好的，我明白了。如果你能使用递归得到正确的配对结果，那么你仍然可以循环遍历最终的配对并求出它们之间的差异总和，或者边遍历边求和。我不确定你目前的代码是什么，因为语法似乎有问题。 - minterm

我认为这个解决方案并不是一个解决方案？它对于某些输入有效，但对于其他输入并没有返回正确的结果。这是因为它假设对于某人来说最近的滑雪场是最优的，但在某些情况下，如果有些人没有得到与他们身高最接近的滑雪场，整体解决方案会更好。 - Grismar

@Grismar，是的，Rivers Shall指出后我已经在那里做了记录。 - minterm

Answer 2

这里有不同的方法，其中一种是暴力破解：

from itertools import combinations


def best_match_brute(skiers, skis):
    all = [list(zip(skiers, c)) for c in combinations(skis, len(skiers))]
    all_with_disparity = [(sum([abs(x-y) for x, y in result]), result) for result in all]
    # assuming the best result is any one with the lowest disparity
    return sorted(all_with_disparity )[0]


def main():
    # making sure the collections are sorted to begin with
    skiers = sorted([6, 11, 13])
    skis = sorted([5, 7, 9, 14])

    # all skiers should be able to get skis
    assert len(skis) >= len(skiers)

    print(best_match_brute(skiers, skis))


if __name__ == '__main__':
    main()

如果您坚持不使用标准库函数，例如itertools.combinations，那么我想您也可以自己编写，但我看不出有什么意义。

def combinations(xs, n):
    if n == 1:
        for x in xs:
            yield [x]
    else:
        while len(xs) >= n:
            x = xs[0]
            xs = xs[1:]
            for c in combinations(xs, n-1):
                yield [x] + c

- Grismar

Answer 3

很抱歉，@minterm发布的算法似乎有误。考虑skiers = [2, 12], skis = [0, 3]。@minterm的程序给出了[(2, 3), (12, 0)]，而最优解是[(2,0), (12, 3)]。@minterm使用的算法是贪心算法，需要严格证明其正确性。

我认为这是一个最大权匹配问题。我们可以将skiers和skis中的元素视为顶点，每个元素skiers[i]和skis[j]之间都有一条权重为abs(skiers[i], skis[j])的边。因此，该示例就像下面的图形：

- Rivers Shall