Output list of numbers based on preference and threshold

Question

I'm looking for some help in finding a suitable algorithm.

Here is my problem:

I have three sets of numbers. Each set represents a preference, and consists of n variables. I want to go over all of the variables in all sets, and output a list of the variables that fall within a given threshold from the highest number overall, from the highest possible set.

set 1: preferred set 2: second-most preferred set 3: last resort.

Threshold: 50

Example 1:

set 1: 100, 110, 120
set 2: 60, 70, 151
set 3 10, 20, 30

Should output: 110, 120 Taken from set 1. 100 should not be included, because the difference between the highest number overall (151) is more than the threshold of 50

Example 2:

set 1: 100, 110, 120
set 2: 100, 120, 161
set 3: 40, 50, 60

Should output: 120 Taken from set 1. 100, 110 should not be included because the difference between those and 161 is more than the threshold of 50.

Example 3:

set 1: 100, 110, 120
set 2: 151, 161, 100
set 3: 110, 120, 130

Should output: 120 Even though 151 and 161 are higher than all of the numbers in set 1, there still is a number that is within the threshold of 50, i.e. 120

Example 4:

set 1: 100, 110, 120
set 2: 151, 161, 200
set 3: 130, 140, 150

Should output: 151, 161, 200

Last example:

set 1: 100, 110, 120
set 2: 151, 161, 171,
set 3: 100, 200, 300

Should output: 200, 300

100 is not chosen because it's less than the threshold from the highest number (300), even though it's within the same set.

Would appreciate any help.

Thanks!

user_3080723 · Answer

This problem is not particularly subtle and doesn't require any particular data structure.

Find the maximum element;
Find the elements in the first set which are above maximum - threshold;
If you found at least one element at the previous step, return the found elements;
Otherwise, repeat with the second set; then the third set.

Example in python:

def find_preferred_numbers(s1, s2, s3, threshold=50):
    m = max(max(s1), max(s2), max(s3)) - threshold
    for s in (s1, s2, s3):
        results = [x for x in s if x >= m]
        if len(results) > 0:
            return results
    return []

examples = [
[[100, 110, 120],
[60, 70, 151],
[10, 20, 30]],

[[100, 110, 120],
[100, 120, 161],
[40, 50, 60]],

[[100, 110, 120],
[151, 161, 100],
[110, 120, 130]],

[[100, 110, 120],
[151, 161, 200],
[130, 140, 150]],

[[100, 110, 120],
[151, 161, 171],
[100, 200, 300]]
]

for i, (s1,s2,s3) in enumerate(examples, start=1):
    result = find_preferred_numbers(s1,s2,s3)
    print('example {}: {}'.format(i, result))

# example 1: [110, 120]
# example 2: [120]
# example 3: [120]
# example 4: [151, 161, 200]
# example 5: [300]

Output list of numbers based on preference and threshold

1 Answers