Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   My own accounting python euler problem (http://www.velocityreviews.com/forums/t704555-my-own-accounting-python-euler-problem.html)

 vsoler 11-07-2009 09:39 PM

My own accounting python euler problem

In the accounting department I am working for we are from time to time
confronted to the following problem:

A customer sends us a check for a given amount, but without specifying
what invoices it cancels. It is up to us to find out which ones the
payment corresponds to.

For example, say that the customer has the following outstanding
invoices: \$300, \$200, \$50; and say that the check is for \$250. This
time it is clear, the customer is paying bills \$200 and \$50.

However, let's now say that the outstanding invoices are \$300, \$200,
\$100 and that the check is for \$300. In this case there are already
two possibilities. The customer is paying the \$300 invoice or the \$200
and \$100. In other words, there is more than one solution to the
problem.

My first question is:
1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
check Ch=600
how can I print all the different combinations of invoices that the
check is possibly cancelling

1.a. first approach using "brute force", that is, exploring all
different combinations: every single invoice, all of 2-element tuples,
3-element tuples, etc...

1.b can all the solutions be found without exploring all possible
combinations? some problems can be solved by discarding some invoices,
for example those whose amounts are greater than the amount of the
check. Any ideas?

My second question is:
2. this time there are also credit notes outstanding, that is,
invoices with negative amounts. For example, I=[500, 400, -100, 450,
200, 600, -200, 700] and a check Ch=600

2.a is the "brute force" method used in 1.a still applicable now that
"I" contains negative values?

2.b same as 1.b. However, this time I can imagen that the number of
invoices that can be discarded is a lot more reduced.

I am a fan of Python, which I find very elegant, powerful and easy to
develop with. I would like to find answers to the problems described
above, partially because I am still learning python, and I would like
to make use of it.

Can anybody help?

 Robert P. J. Day 11-07-2009 09:47 PM

Re: My own accounting python euler problem

On Sat, 7 Nov 2009, vsoler wrote:

> In the accounting department I am working for we are from time to
> time confronted to the following problem:
>
> A customer sends us a check for a given amount, but without
> specifying what invoices it cancels. It is up to us to find out
> which ones the payment corresponds to.
>
> For example, say that the customer has the following outstanding
> invoices: \$300, \$200, \$50; and say that the check is for \$250. This
> time it is clear, the customer is paying bills \$200 and \$50.
>
> However, let's now say that the outstanding invoices are \$300, \$200,
> \$100 and that the check is for \$300. In this case there are already
> two possibilities. The customer is paying the \$300 invoice or the
> \$200 and \$100. In other words, there is more than one solution to
> the problem.
>
> My first question is: 1. given a list of invoives I=[500, 400, 450,
> 200, 600, 700] and a check Ch=600 how can I print all the different
> combinations of invoices that the check is possibly cancelling

that sounds like the classic knapsack problem:

http://www.itl.nist.gov/div897/sqg/d...ckProblem.html

it's NP-complete.

rday
--

================================================== ======================
Robert P. J. Day Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page: http://crashcourse.ca
================================================== ======================

 Robert P. J. Day 11-07-2009 10:13 PM

Re: My own accounting python euler problem

On Sat, 7 Nov 2009, vsoler wrote:

> In the accounting department I am working for we are from time to
> time confronted to the following problem:
>
> A customer sends us a check for a given amount, but without
> specifying what invoices it cancels. It is up to us to find out
> which ones the payment corresponds to.
>
> For example, say that the customer has the following outstanding
> invoices: \$300, \$200, \$50; and say that the check is for \$250. This
> time it is clear, the customer is paying bills \$200 and \$50.
>
> However, let's now say that the outstanding invoices are \$300, \$200,
> \$100 and that the check is for \$300. In this case there are already
> two possibilities. The customer is paying the \$300 invoice or the
> \$200 and \$100. In other words, there is more than one solution to
> the problem.
>
> My first question is:
> 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
> check Ch=600
> how can I print all the different combinations of invoices that the
> check is possibly cancelling

by the way, there's a bit more to it than just seeing if you can
match the cheque amount exactly. some python solutions are here:

http://rosettacode.org/wiki/Knapsack_Problem

and a general solution allows you to place different "values" on which
items you pack into your knapsack.

say a customer has outstanding invoices for 200, 400 and 600, and
you get a cheque for 600. what do you apply that against? the single
invoice for 600, or the two for 200 and 400? that depends.

if all invoices have the same "value", it won't matter. but if the
invoice for 600 just went out, while the two others are just about to
become, say, overdue so that a penalty is about to be applied, your
customer would probably *really* appreciate it if you applied that
cheque to the older invoices.

in general, then, you can not only see what matches exactly but,
for the sake of your customer, you can give higher value to paying off
older invoices. that's how the general knapsack problem works.

rday
--

================================================== ======================
Robert P. J. Day Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page: http://crashcourse.ca
================================================== ======================

 Martin P. Hellwig 11-08-2009 07:27 AM

Re: My own accounting python euler problem

vsoler wrote:
As mentioned in the other answers, your problem is best solved by a long
overdue organisational decision instead of a technical one.

Most popular solutions are:
- All invoices are essential a single credit amount, money coming in is
taken of from the big pile.
- Invoices are split by date, creating multiple credit amounts, any
money coming in is used the pay of the oldest one.

The latter one allows more easily for different interest and penalty rates.

--
MPH
http://blog.dcuktec.com
'If consumed, best digested with added seasoning to own preference.'

 Ozz 11-08-2009 10:43 AM

Re: My own accounting python euler problem

Hi,

> My first question is:
> 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
> check Ch=600
> how can I print all the different combinations of invoices that the
> check is possibly cancelling
>

Incidentally, I'm currently learning python myself, and was working on
more or less the same problem as an exercise;

For listing all different subsets of a list (This is what I came up
with. Can it be implemented shorter, btw?):

def subsets(L):
S = []
if (len(L) == 1):
return [L, []]
else:
for s in subsets(L[1:]):
S.append(s)
S.append(s + [ L[0]])
return S

Now, to use the above piece of code (after 'import subset'):

>>> subset.subsets([4,7,8,2])

[[2], [2, 4], [2, 7], [2, 7, 4], [2, 8], [2, 8, 4], [2, 8, 7], [2, 8, 7,
4], [], [4], [7], [7, 4], [8], [8, 4], [8, 7], [8, 7, 4]]
>>> map(sum,subset.subsets([4,7,8,2]))

[2, 6, 9, 13, 10, 14, 17, 21, 0, 4, 7, 11, 8, 12, 15, 19]

It's not a real solution yet, and as others have pointed out the problem
is NP complete but it might help to get you going.

cheers,
Ozz

 Robert P. J. Day 11-08-2009 12:14 PM

Re: My own accounting python euler problem

On Sun, 8 Nov 2009, Ozz wrote:

>
> Hi,
>
> > My first question is:
> > 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
> > check Ch=600
> > how can I print all the different combinations of invoices that the
> > check is possibly cancelling

>
> Incidentally, I'm currently learning python myself, and was working
> on more or less the same problem as an exercise;
>
> For listing all different subsets of a list (This is what I came up
> with. Can it be implemented shorter, btw?):
>
> def subsets(L):
> S = []
> if (len(L) == 1):
> return [L, []]
> else:
> for s in subsets(L[1:]):
> S.append(s)
> S.append(s + [ L[0]])
> return S
>
> Now, to use the above piece of code (after 'import subset'):
>
> >>> subset.subsets([4,7,8,2])

> [[2], [2, 4], [2, 7], [2, 7, 4], [2, 8], [2, 8, 4], [2, 8, 7], [2, 8, 7, 4],
> [], [4], [7], [7, 4], [8], [8, 4], [8, 7], [8, 7, 4]]
> >>> map(sum,subset.subsets([4,7,8,2]))

> [2, 6, 9, 13, 10, 14, 17, 21, 0, 4, 7, 11, 8, 12, 15, 19]
>
> It's not a real solution yet, and as others have pointed out the
> problem is NP complete but it might help to get you going.

does your solution allow for the possibility of different invoices
of equal amounts? i would be reluctant to use the word "subset" in a
context where you can have more than one element with the same value.

rday
--

================================================== ======================
Robert P. J. Day Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page: http://crashcourse.ca
================================================== ======================

 Ozz 11-08-2009 12:20 PM

Re: My own accounting python euler problem

Oops,

> For listing all different subsets of a list (This is what I came up
> with. Can it be implemented shorter, btw?):
>
> def subsets(L):
> S = []
> if (len(L) == 1):
> return [L, []]

better to check for the empty set too, thus;

if (len(L) == 0):
return [[]]

The order of the sets looks better too;

>>> subset.subsets([1,2,3])

[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]

cheers,

 Ozz 11-08-2009 12:27 PM

Re: My own accounting python euler problem

Robert P. J. Day schreef:
> does your solution allow for the possibility of different invoices
> of equal amounts? i would be reluctant to use the word "subset" in a
> context where you can have more than one element with the same value.

I think it handles different invoices of equal amounts correctly.
I agree with you though that the term subset may not be the best name in
this context because of those duplicates.

cheers,
Ozz

 Dan Bishop 11-08-2009 04:52 PM

Re: My own accounting python euler problem

On Nov 8, 4:43*am, Ozz <notva...@wathever.com> wrote:
> Hi,
>
> > My first question is:
> > 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
> > check Ch=600
> > how can I print all the different combinations of invoices that the
> > check is possibly cancelling

>
> Incidentally, I'm currently learning python myself, and was working on
> more or less the same problem as an exercise;
>
> For listing all different subsets of a list (This is what I came up
> with. Can it be implemented shorter, btw?):
>
> def subsets(L):
> * * * * *S = []
> * * * * *if (len(L) == 1):
> * * * * * * * * *return [L, []]
> * * * * *else:
> * * * * * * * * *for s in subsets(L[1:]):
> * * * * * * * * * * * * *S.append(s)
> * * * * * * * * * * * * *S.append(s + [ L[0]])
> * * * * *return S

You can avoid the S list my making it a generator:

def subsets(L):
if L:
for s in subsets(L[1:]):
yield s
yield s + [L[0]]
else:
yield []

 vsoler 11-08-2009 05:16 PM

Re: My own accounting python euler problem

On Nov 8, 1:27*pm, Ozz <notva...@wathever.com> wrote:
> Robert P. J. Day schreef:
>
> > * does your solution allow for the possibility of different invoices
> > of equal amounts? *i would be reluctant to use the word "subset" in a
> > context where you can have more than one element with the same value.

>
> I think it handles different invoices of equal amounts correctly.
> I agree with you though that the term subset may not be the best name in
> this context because of those duplicates.
>
> cheers,
> Ozz

Ozz,

Instead of subsets, do you mean permutations/combinations? Since 2
invoices can have the same amount perhaps the terms permutation is
better.

Vicente Soler

All times are GMT. The time now is 01:55 PM.