Difference in values between two lists

Question

I'm working on a practice problem, and want to find the minimum disparity between the two lists using recursion.For example, if I have a list, X, with values [79, 85, 10], and a list, Y, with values [78, 80, 87, 12], the disparity will be 4.

I've tried iterating through both lists, and can't figure out how to just find the minimum sum of the disparity, rather than only returning the pairs.

I expect this function to return pairs of skiers and skis, but not the sum representing the minimum disparity between two given lists.

What is the "ski/skier height problem" and how did you calculate that the minimum disparity between those two lists is 4? — jarmod, Apr 02 '19 at 23:59
Sorry for the confusion, I've edited the question a bit to give more information! — user7339685, Apr 03 '19 at 00:05

minterm · Answer 1 · 2019-04-03T06:45:07.157

1

One solution is to use NumPy to find the closest value in the skis list (NumPy function borrowed from Find nearest value in numpy array). Then go through the skiers and find the closest size. Remember to then remove that size from the list.

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)

returns [(6, 5), (11, 9), (13, 14)].

If your goal is to just return the minimum disparity, then iterate through the skier_skis list and sum the difference.

edit: as @Rivers Shall points out, this may not always return the optimal solution.

edited Apr 03 '19 at 06:45

answered Apr 03 '19 at 00:12

minterm

259
3
13

1

Thank you for this solution! I'm trying not to use an built-in Python functions - just simple recursion. But I appreciate your help! – user7339685 Apr 03 '19 at 00:16
Ok, I understand. If you can get it to return the correct pairs using recursion, then you can still loop through the final pairs and sum the differences, or sum them as you go. I'm not sure what you currently have as the syntax appears to be off. – minterm Apr 03 '19 at 00:23
I don't think this solution is a solution? It works for some inputs, but doesn't return the correct result for others. This is because it assumes the nearest ski for someone is optimal, but in some cases, the overall solution is better if some people don't get the ski nearest in height to them. – Grismar Apr 03 '19 at 07:25
@Grismar, yeah I have that noted in there after Rivers Shall pointed that out. – minterm Apr 03 '19 at 17:19

Grismar · Answer 2 · 2019-04-04T00:28:05.767

There's different approaches here, one is to brute-force it:

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()

If you insist on not even using standard library functions like itertools.combinations, then I suppose you could home-brew that as well, but I don't see the point:

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

score 0 · Answer 3 · answered Apr 03 '19 at 03:10

I'm sorry that the algorithm posted by @minterm seems to be wrong. Consider skiers = [2, 12], skis = [0, 3]. The program of @minterm gives [(2, 3), (12, 0)] where the optimal solution is [(2,0), (12, 3)]. The algorithm @minterm uses is a greedy algorithm, which is always in need of rigid proof to justify its correctness.

On my opinion, this is a maximum-weight matching problem. We can view the elements in skiers and skis as vertices and between every element skiers[i] and skis[j] lies an edge with weight abs(skiers[i], skis[j]). So the example is like the following graph:

Difference in values between two lists

3 Answers3