Algorithm For Matching Figures (one-to-many)

Question

This is my first post in stackoverflow.

I need to advise an algorithm for a financial application. Assume we have 2 lists of figures like this (yes, they are bank transactions) :

List 1          | List 2
-------------------------------------
1000            | 200
7000            | 300
3000            | 10000
16000           | 500
                | 16000
                | 4100

I need to match figures with each other considering some conditions:

1. Matches can be one-to-one, one-to-many, or even many-to-many. So, here the two 16000 match (one-to-one), 1000 from list 1 matches 200+300+500 from list 2 (one-to-three), 10000 from list 2 matches 7000+3000 from list 1 (one-to-two), and so on.

2. A figure can be used in more than one match.

3. Number of figures in the two lists may or may not be equal.

4. Maximum number of figures in a one-to-many match should be settable.

5. Many-to-many matches are not a must. But it would be nice if we have them too!

6. Some figures might be left unmatched. It is OK.

What I'm doing to achieve this, is using two complicated nested loops. It works, but as the number of figures, or the maximum number of allowed figures in each match increase, it takes ages to complete!

Are there any better algorithm to do this?

Answer 1

I think I'm right to assert, and SO will give me a kicking if I am wrong, that the kernel of your computation is NP-hard, which means that you are (very) unlikely to find a polynomial-time solution to it. Your kernel is, given a single number (such as 10000) and a list of other numbers, find all the subsets of the list which sum to the single number.

This kernel is a variation of the subset sum problem.

Given that, there are limitations on how much better an algorithm you can find, and your expectations of finding a 'fast' algorithm are likely to be disappointed.

To make your algorithm faster, I'd suggest you start by sorting both lists. Take the first number from list 1, from list 2 take all the numbers less than or equal to the number from list 1, figure out the matches, repeat ... Then work down list 2 number by number ...