Finding the smallest n values that are at least x apart in a list

This is a complicated job, we would want to build a list of indices where the first entry is the index of the smallest value in list_of_numbers and every next entry in this index_list points to the next highest value in list_of_numbers manipulating this type of list would be much easier and efficient. We could do the following:

index_map=dict()
for i in range(len(list_of_numbers)):
    value=list_of_numbers[i]
    if value in index_map:
        index_map[value]+=[i]
    else:
        index_map[value]=[i]
sorted_values = sorted(index_map)

Now we have a dictionary of every unique value in list_of_numbers that maps to all the indices that point to it. We also have a list that goes from the smallest unique value to the largest. We can now build our index_list:

index_list=[]
for value in sorted_values:
    index_list+=index_map[value]

del index_map, sorted_values

All that is left to do is iterate left to right in our index_list and find the first combination of indices that have the appropriate gap. This is much easier and faster to compute in an algorithm.

Unfortunately it is not possible to have a time complexity less than O(n) because you need to check every entry in list_of_numbers to find the smallest entry.

I did this using a recursive function but you can definitely optimize this and make the algorithm smarter:

def gap_selecter(numlist, n_many, gap):

if numlist==None:          # Fast exit if recursion fails
    return None

x=numlist[0]
speudolist=numlist[1:]
                    
if n_many==1:              # base case
    return [x] 
                            

else:
    for i in range(len(speudolist)):
        
        if abs(x-speudolist[i])>=gap:   #recursive step occurs here
            
            recursion_list = gap_selecter(speudolist[i:], n_many-1, gap)   
            
            if recursion_list !=None:
                return [x]+recursion_list

return None                # if we find no possible list we return None

Here is everything put together.

def smallest_values(list_of_numbers: list, n_many: int, x_apart: int):

index_map=dict()
for i in range(len(list_of_numbers)):
    value=list_of_numbers[i]
    if value in index_map:
        index_map[value]+=[i]
    else:
        index_map[value]=[i]
sorted_values = sorted(index_map)

index_list=[]
for value in sorted_values:
    index_list+=index_map[value]

del index_map, sorted_values

final_indices=gap_selecter(index_list, n_many, x_apart)
if final_indices==None:
    return None

final_numbers=[]
for i in final_indices:
    final_numbers+=[list_of_numbers[i]]

return final_numbers

values_simple = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
values_complex = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]
d = 2
n = 5

test_simple = smallest_values(values_simple, n, d)       # [-10107, -9995, -2009, -659, -12]
test_complex = smallest_values(values_complex, n, d)     # [-9995, -9995, -2009, -659, -83]

The key problem here is breaking ties on duplicate values, such as -9995 in the example. We basically need to try picking them in different order, and check which one produces the sequence with the next lower value (or if the next value is the same, then the one after that, and so on).

One way to do it is with recursive search:

from collections import defaultdict

# find the next smallest and return all locations of that number
# that can be used (i.e. not within d from the previously used values)
def get_next(vs, vd, d, skip):
    for v in vs:
        os = []
        for l in vd[v]:
            if not any([l>x-d and l<x+d for x in skip]):
                os.append((l, v))
        if len(os) > 0:
            return os
    return None

# recursive search
def r(vs, vd, n, d, skip=[], out=[]):
    if len(out) >= n:
        return out
    
    os = []
    for (l, v) in get_next(vs, vd, d, skip):
        o = r(vs, vd, n, d, skip+[l], out+[v])
        os.append(o)
    mo = min(os)
    return mo

# main func
def smallest_values(values, n, d):
    vd = defaultdict(list)
    for l, v in enumerate(values):
        vd[v].append(l)
    vs = sorted(vd.keys())
    return r(vs, vd, n, d, [], [])

Test on provided examples:

values_simple = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
values_complex = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]

print('simple:  ', smallest_values(values_simple, 5, 2))
print('complex: ', smallest_values(values_complex, 5, 2))

Output:

simple:   [-10107, -9995, -2009, -659, 13]
complex:  [-9995, -9995, -2009, -659, -82]

A timing test on a 1,000,000 value list (800ms, so about 15min for 1,000 lists single-threaded):

%%time
vs = np.random.randint(0, 1000000, 1000000)
smallest_values(vs, 5, 2)

Output:

CPU times: user 780 ms, sys: 20.8 ms, total: 800 ms
Wall time: 800 ms
[3, 5, 6, 7, 8]

P.S. This finds the sequence having the lowest value earlier in the sequence. For example, it will prefer [1, 2, 100] over [1, 3, 4] (both have 1 in position 1, but the first sequence has 2 < 3 in position 2). IIUC this is what is expected, based on your comment I guess the logic would be worded as, is there a selection of the previous chosen values that allows the next smallest value to be chosen.

//EDIT: Ahh, now I see. The keyphrase is (assuming we take the first and last -9995 and ignore the second to last)

The big issue is that you cannot pick any duplicate value (in your example the second last -9995 in the list). Instead, you want to pick duplicate values such that your last element (or the sum of the resulting list?) is minimal, correct?

To me, this sounds like an restricted optimization problem. I'm not even sure if it has the same result depending on what you define as "optimal" (either the sum or the last element or something else...)