Apologizing for the novel below, but i wanted to explain this quite complex issue (for me) and ask for help: I have two lists of payments, one is about payments Sent and the second about payments Received. Some Received payments are summed together, so e.g. in Sent list I see amounts 1.22, 2.33, 3.77, 4.11. In Received I see 3.55, 4.11, 13.27. So the result is that sum of 1.22+2.33 from Sentlist matches Received 3.55. Item 4.11 is one single payment 1:1 and 13.27 remains as unmatched in Received. Payments Sent are declared as sent, but it is not guaranteed that all of them were really Received. Some Received payments could be from other sources than author of Sent list, so unmatched items in both Received and Sent lists are expected.
The 1st issue is that this task can have multiple solutions: e.g. if Sent contains 1.11,2.22,3.33,5.55 and Received contains 3.33,7.77, I do not know whether received amount 3.33 matches to two sent items(1.11+2.22) or one sent item(3.33). My code below does not address this issue at all, but due to this also the order of items in lists determines the result. Task here would be to find two border combinations with minimalized/maximalized sum of unmatched Sent items (which can be different to minimalized/maximalized amount of unmatched Sent item).
The 2nd, more important issue, is that I use deleting of matched elements from both lists during the matching comparison/iterations and very likely it needs more intelligent redesign. Reset of variable ircvd to 0 after each rcvd list deletion seems sufficient to match all single-amount items, but maybe there is some more clever way, because this way I iterate also over those items, which already were tested. This was about the iterations over Received list.
But iteration over Sent list also need some kind of refresh to start generating combinations over updated list after the deletion. Otherwise I see wronglymatched items, because they contain already used items, supposed to be already deleted - 99.05 in following example (brackets contain sent items, total is received amount) already contributed to received amount 1046.27, so it cannot be used for 653.92:
-------MATCHED: (12.43, 91.94, 386.99, 630.95) as total: 1122.31
-------MATCHED: (9.6, 18.11, 106.86, 332.99, 630.38) as total: 1097.94
-------MATCHED: (10.17, 20.43, 99.05, 262.7, 653.92) as total: 1046.27
-------MATCHED WRONGLY: (15.23, 22.77, 44.86, 99.05, 472.01) as total: 653.92
Not sure how to do initialization of combination generator without starting from the beginning.
Empirically I sorted Received list in descending order to find solution more quickly (multiple smaller Sent items summed into higher Received amount), otherwise it starts with combinations far from matching amounts and takes ages to finish. Now it is finished in couple of seconds.
I will appreciate suggestion how to deal with this (mainly iterations over both rcvdlist and sentlist used with combinations) and review whether something was not omitted. Solution for the 1st issue (multiple results) is maybe beyond reasonable computing time and/or memory.
Thanks for any ideas.
Peter.
from operator import itemgetter
from itertools import combinations
rcvd = [6.83,8.36,9.97,11.81,14.97,27.23,33.63,39.09,40.75,91.35,91.83,99.05,109.30,135.10,158.82,161.02,164.50,174.51,196.55,249.29,262.17,283.29,309.26,311.02,317.28,367.51,417.41,491.31,557.08,559.88,569.00,653.92,1046.27,1097.94,1122.31]
sent= [9.60,9.97,10.17,12.43,14.97,15.23,17.28,18.11,20.22,20.43,22.55,22.77,25.67,27.23,29.40,30.47,33.63,39.09,40.05,42.85,44.86,53.11,66.67,70.70,91.35,91.83,91.94,93.71,96.99,99.05,106.86,116.99,124.35,131.56,146.24,158.82,161.02,182.62,196.55,254.19,262.70,276.87,309.74,332.99,386.99,472.01,547.48,630.38,630.95,653.92,984.45]
#sent= [9.60,9.97,10.17,12.43,15.23,17.28,18.11,20.22,20.43,22.55,22.77,25.67,27.23,29.40,14.97,30.47,33.63,39.09,40.05,42.85,44.86,53.11,66.67,70.70,91.35,91.83,91.94,93.71,96.99,99.05,106.86,116.99,124.35,131.56,146.24,158.82,161.02,182.62,196.55,254.19,262.70,276.87,309.74,332.99,386.99,472.01,547.48,630.38,630.95,653.92,984.45]
# this sentlist is not sorted, 14.97 is in ~30.00 fore debug
rcvd=sorted(rcvd,reverse=True)
sent=sorted(sent)
print("len rcvd",len(rcvd))
print("len sent",len(sent))
print("sum rcvd",sum(rcvd))
print("sum sent",sum(sent))
maxrcvd=max(rcvd)
print ("max rcvd",maxrcvd)
ircvd=0 # counter over rcvd list
#for ircvd in range (0,len(rcvd)):
while ircvd < len(rcvd):
print("ircvd:",ircvd)
for isent in range(1, len(sent)+1): #isent is number of amounts to be summed
for comb in combinations(sent, isent): #create combination of amounts from sent list
sumcomb=sum(comb) #summed sent items
if sumcomb<maxrcvd+1: #maybe not necessary, too high sum of sent payments -> skip
if sumcomb == rcvd[ircvd]: #if sum of sent amounts found in rcvd list
print("----------------------------------")
match=True #flag that match was found or not
for ind in range(0,len(comb)):
if comb[ind] not in sent: #this should not happen, iterating issue?
match=False
print("-------MATCHED WRONGLY:",comb," as total:",rcvd[ircvd])
if match==True:
print("-------MATCHED:",comb," as total:",rcvd[ircvd])
for ind in range(0,len(comb)):
sent.remove(comb[ind]) #removal of used particular sent payments
rcvd.remove(rcvd[ircvd]) #removal of one received payment
ircvd=0 # !!! otherwise unmatched items remain in final lists - without this line, some single-amount items 14.97 and 158.02 will remain in uncleared lists
print("ircvd:",ircvd)
ircvd=ircvd+1 # go to another received payment
rcvd=sorted(rcvd)
sent=sorted(sent)
print ("uncleared rcvd",rcvd)
print ("uncleared sent",sent)
print ("uncleared rcvdsum",sum(rcvd))
print ("uncleared sentsum",sum(sent))