# algorithms – FInding the unique top sums from multiple lists

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 where 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 duplicates sums, so the research for the uniques one 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))

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

Is there a way to design an algorithm with a lower complexity?

Posted on