Looking for the fastest way to divide dictionary keys (based on values) into lists of list such that-CodePudding

I have an OrderedDictionary a = {"1":800, "2":400, "3":600, "4":200, "5":100, "6":400}

I would like to divide the keys into a list of lists such that each list's total values do not exceed a threshold value (600 in this case) or if a value is greater than the threshold value it should have its own list. Also, we only check for the next key (like a sliding window).

The above dictionary should return expected = [['1'], ['2'], ['3'], ['4', '5'], ['6']]. For example, '1' has its own list since it is greater than threshold. '2' has its own list since values of '2' '3' is greater than threshold. ['4', '5'] has values totalling up to 600 and if we append '6', it exceeds the threshold.

Here is what I have so far:

def check_result(a):
    
    result = {}
    curr_val = 0 
    threshold = 600
    l =[]
    result = []

    for i in a.keys():
        if curr_val >= threshold:
           result.append(l)
           l = []
           curr_val = 0

        if curr_val   a[i] > threshold:
          result.append(l)
          l = [i]
          curr_val = a[i]
        else:
          l.append(i)
          curr_val  = a[i]

    

   result.append(l)
   print(result)

It gives the output as [[], ['1'], ['2'], ['3'], ['4', '5'], ['6']].

Looking for a correct solution in O(n) time.

Thanks!

CodePudding user response：

The second if should just have an extra check that l is not empty:

if curr_val   a[i] > threshold and l:

CodePudding user response：

Slightly less cumbersome code:-

a = {"1": 800, "2": 400, "3": 600, "4": 200, "5": 100, "6": 400}


def check_result(d):
    T = 600
    result, e = [], []
    s = 0
    for k, v in d.items():
        if e:
            if s   v > T:
                result.append(e)
            else:
                e.append(k)
                s  = v
                continue
        e = [k]
        s = v
    if e:
        result.append(e)
    return result


print(check_result(a))

CodePudding user response：

Based on the running sum, you can streamline the code by toggling the list to append keys to between the whole result and its last sublist.

a =  {"1":800, "2":400, "3":600, "4":200, "5":100, "6":400}
t = 600  # Treshold

r = []   # result, list of lists of keys
s = 0    # running sum
for k,v in a.items():
    group,item,delta = (r[-1],k,v) if r and s v<=t else (r,[k],v-s)
    group.append(item)  # append to result or last sublist
    s  = delta          # update running sum

print(r)
[['1'], ['2'], ['3'], ['4', '5'], ['6']]

Or this somewhat shorter (but less efficient) variant:

r,s = [],0   # result, running sum
for k,v in a.items():
    r  = [r.pop(-1) [k] if r and s v<=t else [k]]
    s  = v - s*(s v>t)