Поиск уникальных топ-сумм из нескольких списков

Мой вопрос возникает из эта почта на MSE, где я дал ответ на вопрос:

Дано несколько списков. Количество списков произвольное. Каждый список содержит числа и отсортирован по убыванию. Мы возьмем ровно $ 1 $ элемент из каждого списка и вычислите сумму элементов. Как бы вы попытались найти верхний $ N $ суммы?

Здесь не обязательно должны быть разные верхние суммы, а должны быть только их индексы. Я хотел написать алгоритм, чтобы найти топ $ N $ уникальные суммы, а именно там, где сумма элементов различна. Я использовал тот же подход, который описан в связанной публикации. Проблема в том, что для некоторых исходных данных существует множество повторяющихся сумм, поэтому поиск уникальных данных становится все медленнее и медленнее. Выкладываю реализацию на питоне

import time

def top_solutions_2(N,lists):

    N_best = []
    k, len_k_lists = len(lists), [len(x) for x in lists]
    init_sol = (sum(x[0] for x in lists),tuple(0 for x in range(k)))
    comp_list, new_vals = [[init_sol]], []
    seen = {init_sol[1]}

    for _ in range(N) :

        curr_best = [float('-inf')]
        for x in comp_list :
            if x and x[-1][0] > curr_best[0] : curr_best = x[-1]

        N_best.append(curr_best)

        inds = []

        for arr in comp_list : 

            while arr :
                
                comp_val = arr.pop()
                
                if curr_best[0] > comp_val[0] : arr.append(comp_val); break
                
                inds.append(comp_val[1])

        comp_list.append([])
        
        for ind in inds :
            
            for x in range(k) :

                if len_k_lists[x] > ind[x]+1 : r = tuple(c if i != x else c+1 for i,c in enumerate(ind))
                else : continue

                if r not in seen :
                    curr_sum = curr_best[0]+lists[x][r[x]]-lists[x][r[x]-1]
                    comp_list[-1].append((curr_sum,r))
                    seen.add(r)                
                
        comp_list[-1].sort()

    return N_best
        
for N in range(10,60,10) :

    lists = [ [23,5,3,2,1],
              [19,9,8,7,0],
              [17,12,4,2,1],
              [15,13,11,9,2],
              [21,17,13,9,4],
              [16,13,12,11,1],
              [27,23,21,18,4],
              [31,25,24,12,1],
              [27,22,14,7,3],
              [9,8,7,6,5]]

    a = time.time()
    top_solutions_2(N,lists)
    b = time.time()
    print("Top {} in {} sec".format(N,b-a))

где выход

Top 10 in 0.0 sec
Top 20 in 0.07787561416625977 sec
Top 30 in 0.5308513641357422 sec
Top 40 in 2.2048890590667725 sec
Top 50 in 7.203002452850342 sec

Как можно сделать более эффективный алгоритм с меньшей сложностью и / или меньшим временем работы? А также, как можно повысить эффективность моего подхода?

заранее спасибо

Я написал новое решение проблемы, основанное на тех же принципах кода в моем вопросе, но на этот раз с использованием словаря с ключами, равными видимым суммам, и индексами в качестве значений. Это лучше, потому что мне не нужно ничего сортировать, в то время как в другом решении мне нужно сортировать каждый новый добавленный список, а также мне не нужно вставлять максимальные элементы в каждый список, я просто перебираю индексы из max_sum.

def top_solutions_2(N,lists):
    N_best = []
    k, len_k_lists = len(lists), [len(x) for x in lists]
    max_sum = sum(x[0] for x in lists)
    comp_dict = {max_sum : [tuple(0 for x in range(k))]}
    seen = {comp_dict[max_sum][0]}

    for _ in range(N) :

        N_best.append((max_sum,comp_dict[max_sum][0]))
        new_max = float('-inf')

        for ind in comp_dict[max_sum] :
            
            for x in range(k) :

                if len_k_lists[x] > ind[x]+1 : r = tuple(c if i != x else c+1 for i,c in enumerate(ind))
                else : continue

                if r not in seen :
                    
                    curr_sum = max_sum+lists[x][r[x]]-lists[x][r[x]-1]

                    if curr_sum > new_max : new_max = curr_sum
                    
                    if curr_sum not in comp_dict : comp_dict[curr_sum] = [r]
                    else : comp_dict[curr_sum].append(r)
                        
                    seen.add(r)

        comp_dict.pop(max_sum)
        max_sum = new_max
                
    return N_best     

Он немного лучше по производительности: при N = 80 и тех же списках другого решения это выполняется примерно за 60 секунд, а другое примерно за 100 секунд.

Я думаю, что просто новый способ уменьшить пространство поиска повысит производительность на соответствующую величину, но я не уверен, как этого добиться.

Я не уверен, подходят ли ваш пост и мой ответ к обзору кода, потому что речь идет о разработке алгоритмов. Но вот мое предложение по лучшему алгоритму. Используйте динамическое программирование, как это делает мой медленный CAS, умножая слева направо.

(%i15)  (x^9+x^8+x^7+x^6+x^5)*(x^15+x^13+x^11+x^9+x^2)*(x^16+x^13+x^12+x^11+x)*(x^17+x^12+x^4+x^2+x)*(x^19+x^9+x^8+x^7+1)*(x^21+x^17+x^13+x^9+x^4)*(x^23+x^5+x^3+x^2+x)*(x^27+x^22+x^14+x^7+x^3)*(x^27+x^23+x^21+x^18+x^4)*(x^31+x^25+x^24+x^12+x), expand;
Evaluation took 0.3906 seconds (0.3999 elapsed) using 1.737 MB.
(%o15)  x^205+x^204+2*x^203+3*x^202+7*x^201+10*x^200+16*x^199+22*x^198+32*x^197+46*x^196+63*x^195+86*x^194+111*x^193+147*x^192+185*x^191+240*x^190+299*x^189+377*x^188+458*x^187+566*x^186+684*x^185+832*x^184+998*x^183+1198*x^182+1424*x^181+1681*x^180+1984*x^179+2323*x^178+2729*x^177+3159*x^176+3665*x^175+4200*x^174+4838*x^173+5516*x^172+6296*x^171+7124*x^170+8067*x^169+9079*x^168+10206*x^167+11441*x^166+12794*x^165+14277*x^164+15859*x^163+17612*x^162+19469*x^161+21536*x^160+23690*x^159+26067*x^158+28532*x^157+31226*x^156+34016*x^155+37030*x^154+40181*x^153+43503*x^152+46960*x^151+50574*x^150+54399*x^149+58318*x^148+62441*x^147+66633*x^146+71075*x^145+75517*x^144+80157*x^143+84816*x^142+89656*x^141+94450*x^140+99306*x^139+104175*x^138+109042*x^137+113903*x^136+118633*x^135+123410*x^134+127975*x^133+132545*x^132+136833*x^131+141134*x^130+145121*x^129+149024*x^128+152623*x^127+156096*x^126+159287*x^125+162190*x^124+164887*x^123+167197*x^122+169335*x^121+170943*x^120+172463*x^119+173393*x^118+174221*x^117+174442*x^116+174604*x^115+174190*x^114+173616*x^113+172588*x^112+171336*x^111+169705*x^110+167725*x^109+165584*x^108+162978*x^107+160261*x^106+157026*x^105+153909*x^104+150226*x^103+146659*x^102+142597*x^101+138750*x^100+134440*x^99+130219*x^98+125758*x^97+121379*x^96+116816*x^95+112165*x^94+107623*x^93+102964*x^92+98456*x^91+93757*x^90+89435*x^89+84873*x^88+80597*x^87+76125*x^86+72062*x^85+67811*x^84+63813*x^83+59784*x^82+56067*x^81+52360*x^80+48788*x^79+45413*x^78+42168*x^77+39094*x^76+36034*x^75+33312*x^74+30608*x^73+28148*x^72+25669*x^71+23529*x^70+21382*x^69+19446*x^68+17551*x^67+15916*x^66+14326*x^65+12869*x^64+11538*x^63+10365*x^62+9281*x^61+8241*x^60+7346*x^59+6504*x^58+5751*x^57+5004*x^56+4397*x^55+3813*x^54+3309*x^53+2833*x^52+2472*x^51+2135*x^50+1845*x^49+1581*x^48+1362*x^47+1153*x^46+956*x^45+792*x^44+649*x^43+533*x^42+426*x^41+354*x^40+291*x^39+247*x^38+199*x^37+163*x^36+128*x^35+98*x^34+71*x^33+51*x^32+39*x^31+28*x^30+21*x^29+16*x^28+14*x^27+10*x^26+7*x^25+5*x^24+3*x^23+x^22

Если мой пост непонятен, скажите, пожалуйста.