I didn't check your maths but I have some code now and I'm pretty certain that the complexity is 2^n - 1 which means for 15 unpaid invoices there are 32767 combinations to check i.e 32767 combinations of unpaid invoices to check against the value just paid by the unhelpful customer.

like I said previously if you have 1 bit for every unpaid invoice e.g 5 unpaid invoices gives a number with 5 bits then counting from 1 to this number will give you every combination of bit patterns for that number of bits...well 5 invoices gives 5 bits which is 2^5 which is 32, subtract 1 to get the number with 5 bits and discount 0.....so you end up with the number 31(5 bits set) from 1 to 31 each iteration gives you a bit pattern which corresponds to the invoice index in the list of invoices. just go through and check every combination against the amount paid, and you will find the combination that adds up to the payment...

this is trivial IMO, and certainly from an O(order of complexity position)
edit: I tried it with 6 as well so it passes proof by induction...

@martin
I just edited out my comment about your equation....I'm still creeping up on the logic...
are you saying thats the order of complexity if the value just received related to 5 invoices in the list?

My edited response originall said I think your equation relates to combinations where every position might be filled, e.g

you have the list abcd so every combination of those 4 entries being present. I was thinking it may not consider if only one, or two, or three of the entries was present. I thought your factorial equation looked similar to the wiki equation, which does only consider combinations where every item in the list is present.

still pondering...

If Mike is serious about this and tells me what format his list is in then he can have the code/app.

edit: the other thing that I thought about was.......there is no mention of how many invoices the received payment relates to. I was making no assumptions about this so the method I outlined covers any amount of invoices being included in the payment, with the addition that it will find any duplicate combinations that add up to the payment...

it's deffo a good question.

42

Thanks Ed, much appreciated.

These are now in the past, but may have a similar problem in the future.

It is possible invoice values could be the same, but quite unlikely.

5 total to check out is easy. I can look and find or cut and paste into Excel and twiddle.

Problem comes when we have a few o/s from Month 1, 50 from Month 2 and 60 from Month 3. There may even be a month 4.

They could be paying up some or all of the old ones with and/or some current ones. They are a law to themselves.

When reaching a halt in programming I find a trip to the loo nearly always works wonders
I work in the wonderful FoxPro, can export easily into Excel
Think I could programme this into Fox given time, which I don't have - unless I go to the loo more often !

Ed and Martin

I'm serious and so is my accountant as he has the same problem X times over.
If there were only 15 to choose a selection of say 5 I can do that fairly easily.
Knocking out the big ones that exceed the payment reduces that 15.
The bigger ones, if when added to the smallest exceed the total can also be knocked out.

Wow
Thanks Ed.

You like sums !
Numbers have a fascination and you/we can read more into them.
To manipulate them is even cooler.
I still like programming in FoxPro and database twiddling.

We were keen at school on Maths. Had such a good teacher a bundle of us made Grade 1 Maths O level at 15.

What is this code plugged into, and how do I use it ?

Thanks again

I'm about the only punter in the world who doesn't have a mobile
Can I plug this code into something on the pc ?

(Programming in FoxPro is about all I am competent to do BTW)

Thanks Ed. I can happily wait a couple of days

We have an exclusive non phone club of 2 !

Swap to BB code for easier or use Reply in the white box.
If I back space in Quote I go into the original and can't get out. Have to cancel and try again

Hi Mike
there has been a delay with this, life has conspired to get in the way.....

I now have an initial working version(see below). A couple of things to note:
a) its all too easy to get multiple solutions(this version doesn't address this situation)
b) the problem complexity is exponential, depending on muber of unpaid invoices. The following maximum times show the issue:
examples:

n = 20 takes 0.19 seconds
n = 25 takes 6.05 seconds
n = 32 takes 945.9 seconds

be aware that these are amaximum times, if a solution exists then it will usually be found well under the maximum time.

the current version only has 2 threads running. This could be increased to halve the problem space. The current version only allows for 32 unpaid invoices. Increasing this would necessitate adding extra threads otherwise the elapsed times wouldn't be practical. Extra threads takes development time which I will do if you are still interested, but it won't happen for a while.

If you want to play with this version I will send a link to the zip in a message. This one is 32 bit windows tested on win7.