Finding unique top sums from multiple lists

Question

My question arises from this post on MSE where I have provided an answer to solve the question :

There are multiple lists given. The number of lists is arbitrary. Each list contains numbers and is sorted descendingly. We shall take exactly \$1\$ element from each list and calculate the sum of elements.How would you go about finding the top \$N\$ sums?

Here the top sums need not to be different, just the indices of them. I wanted to write an algorithm to find the top \$N\$ unique sums, namely where the sum of elements is different. What I have done is using the same approach described in the linked post. The problem is that for some inputs there are lots of duplicate sums, so the research for the unique ones gets slower and slower. I post the implementation in python

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

where the output is

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

How can a more efficient algorithm with a lower complexity and/or a lower running time be made?And also, how can my approach be improved in efficiency?

Thank you in advance

Answer 1

I am not sure if your post and my answer fits to code review because it is about algorithm design. But here is my proposal for a better algorithm. Use dynamic programming as my slow CAS does by multiplying from left to right.

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

If my post is not clear please tell me.

Answer 2

I have written a new solution to the problem based on the same principles of the code in my question, but this time using a dictionary with keys equal to the seen sums and the indices as values. This is better because I don't need to sort anything, while in the other solution I need to sort every new list added, and also, I don't need to pop the max elements in each list, I just iterate through the indices of 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     

It is slightly better in performance : with N = 80 and the same lists of the other solution, this one executes in about 60 seconds, while the other in about 100 seconds.

I think that just a new way to reduce the search space will improve the performance by a relevant amount, but I'm not sure how to achieve this.

Answer 3

If each list is sorted in descending order, I don't see why you need seen lists at all. Like the previous post https://math.stackexchange.com/questions/4122113/finding-the-top-sums-of-values-from-multiple-lists you will always move to the next highest term in the list that reduces the sum the least -- ie, argmin{k}(list_k[x+1]-list_k[x]). Just that instead of moving once in list_k, you move while (list_k[x+1]==list_k[x])

Alternatively, you could just remove duplicates from the lists at the beginning and then just use your previous solution