Cumulative sum to match a groupby result

Question

I have three dataframes:

"df_sim" - indicates customers (Cust1) who have made payments to our company that do not match our invoices due to some incorrect data. Therefore, I am trying to match those to some payments made by other customers with a similar (or equal) name (Cust2).
"df_inv" - invoices issued by our company to the customers ("Cust1" of the table "df_sim") along with the date and amount details.
"df_paym" - that includes the payments that my company has in the system from customers (Cust2) of table "df_sim".

Therefore, the sum of the invoice amounts for each customer (df_inv) must be grouped (regardless of the date, as long as df_inv['Date] <= df_paym['Date']) and checked against the table "df_paym" within a threshold of $1, which may also contain some additional payments that should be disregarded. Therefore, the invoice amounts should be checked against all possible combinations of payments, until the amount of the invoice is reached.

If a match is found, i.e. for Cust1 & Cust2 "ABC" (1st row in "df_sim"), rows 2 and 3 should be skipped.

The expected output would be as below (column "Match (Y/N)").

df_sim: (SIMILARITY BETWEEN CUSTOMERS)

| Cust1 | Cust2| Similarity% | Match (Y/N) | 
|  ABC  |  ABC |    1.00     |      Y      |  
|  ABC  |  ABB |    0.66     |      N      |
|  ABC  |  AYZ |    0.33     |      N      |
|  DEF  |  DEA |    0.66     |      N      |
|  DEF  |  DEB |    0.66     |      Y      |
|  DEF  |  DEC |    0.33     |      N      |
|  GHI  |  GAB |    0.33     |      Y      |
|  LMN  |  LMA |    0.66     |      N      |
|  LMN  |  LAB |    0.33     |      Y      |
|  OPQ  |  OPA |    0.66     |      Y      |

df_inv: (INVOICES)

| Cust1 | Amount  |  Date  | Match (Y/N) | 
|  ABC  |  10.00  |01/01/21|     Y       |
|  ABC  |  10.00  |01/01/21|     Y       |
|  ABC  |  29.50  |01/01/21|     Y       |
|  DEF  |  40.00  |01/02/21|     Y       |
|  GHI  |  49.00  |01/02/21|     Y       |
|  GHI  |  10.00  |01/02/21|     Y       |
|  LMN  |  100.00 |01/03/21|     Y       |
|  LMN  |  0.99   |01/03/21|     Y       |
|  OPQ  |  190.00 |01/03/21|     Y       |
|  OPQ  |  10.99  |01/03/21|     Y       |

df_paym: (PAYMENTS)

| Cust1 | Amount  |  Date  | Match (Y/N) |
|  ABC  |  50.00  |01/02/21|     Y       |
|  ABB  |  50.00  |01/02/21|     N       |
|  DEA  |  40.00  |31/12/20|     N       |
|  DEB  |  40.00  |01/03/21|     Y       |
|  GAB  |  60.00  |01/03/21|     Y       |
|  LMA  |  98.00  |01/04/21|     N       |
|  LAB  |  100.99 |01/04/21|     Y       |
|  OPA  |  200.00 |01/04/21|     Y       |

I have drafted some code but the problem seems more complicated than expected. I was only able to match the figures that match perfectly between invoices & payments but not to write the "date" condition & try to calculate all the combinations.

import pandas as pd

df_sim = pd.DataFrame({'Cust1':['ABC', 'ABC', 'ABC', 'DEF','DEF','DEF','GHI', 'LMN', 'LMN', 'OPQ'],
        'Cust2': ['ABC', 'ABB', 'AYZ', 'DEA', 'DEB', 'DEC', 'GAB', 'LMA', 'LAB', 'OPA'],
        'similarity%': [1, .66, .33, .66, .66, .33, .33, .66, .33, .66]})


 df_inv = pd.DataFrame({'Cust1':['ABC', 'ABC', 'ABC', 'DEF', 'GHI', 'GHI', 'LMN', 'LMN', 'OPQ', 'OPQ'],
            'Amount': [10, 10, 29.5, 40, 49, 10, 100, 0.99, 190, 10.99],
            'Date': ['01/01/2021', '01/01/2021', '01/01/2021','01/02/2021', 
                  '01/02/2021','01/02/2021','01/03/2021','01/03/2021','01/03/2021','01/03/2021']})

df_paym = pd.DataFrame({'Cust1':['ABC', 'ABB', 'DEA', 'DEB', 'GAB', 'LMA', 'LAB', 'OPA'],
        'Amount': [50, 50, 40, 40, 60, 98, 100.99, 200],
        'Date': ['01/02/2021', '01/02/2021', '31/12/2020', '01/03/2021', 
              '01/03/2021', '01/04/2021', '01/04/2021','01/04/2021']})

df_inv_grpd = df_inv.groupby(['Cust1', 'Date'])['Amount'].sum().reset_index()


for cust1, cust2 in zip(df_sim['Cust1'], df_sim['Cust2']):
    if df_inv_grpd[df_inv_grpd['Cust1']==cust1]['Amount'].values in (df_paym[df_paym['Cust1']==cust2]['Amount'].to_numpy()):
        print(cust1, " ", cust2, " ", ":", 'OK')
    else:
        print(cust1, " ", cust2, " ", ":", 'NO')

user_19330078 · Answer

Okay, there are many combinations of how payments and invoices match. An incomplete heuristic would for example look like the following:

matched_custs = set()
for cust1, cust2 in zip(df_sim['Cust1'], df_sim['Cust2']):
    inv_cust1 = df_inv_grpd[df_inv_grpd['Cust1']==cust1][['Date','Amount']].values
    for date, inv_amount in inv_cust1:
        pay_cumsum = df_paym[
                 (df_paym['Cust1']==cust2) & (date <= df_paym['Date'])
                        ].sort_values(by=['Date'])['Amount'].to_numpy().cumsum()
        flagged_payments = pay_cumsum>=inv_amount
        if (
            sum(flagged_payments) 
            and abs(inv_amount-pay_cumsum[flaged_payments][0]) < 1
            and (cust1,date) not in matched_custs
            ):
            matched_custs.add((cust1,date))
            # TODO: indicate in both tables that invoices 
            # and the flagged_payments are matched
            # to ignore them from now on. 
            print(cust1, " ", cust2, " ", ":", 'OK')
        else:
            print(cust1, " ", cust2, " ", ":", 'NO')

The example above just shows one approach to applying the date-condition. It is simply trying to find a match in the cumsum over the considered sorted payments for grouped invoices by Date and Customer. Instead, one could ask for all combinations (also non-consecutive ones) to meet the 1$ condition. That is also known as the subset sum problem. Precisly, when asking for an exact match (0$ difference) or a variant of the knapsack problem. There are well-working dynamic algorithms for that, but one should consider their running times as they are in general NP-hard.

Cumulative sum to match a groupby result

1 Answers