Good suggestion Navneet.. I had a similar solution but am looking for something more faster. Performance is a major consideration to me. The possible permutations for a large set of debits and credits could be massive. The solution should be intelligent enough to discard non-possible branches quickly.
On Tue, Jun 7, 2011 at 11:15 PM, Navneet Gupta <[email protected]>wrote: > Well, one approach is have all possible sums stored for debits and > credits and match the sums. > > Basically, you can create a multi-list type DS (if i remember the name > correctly) and store the SUMS and with formative elements in linked > lists being pointer by node containing sums > > SUM 1 -> Header 1 -> Header 2 -> Header 3 > > Header1 -> Debit m -> Debit n (Here one of the possibilities of > forming a sum SUM 1 is Debit m + Debit n) > > Now, it's basically a design choice whether you want to have a single > DS like above to contain both Credit and Debit based calculations or > have separate multi-lists for Debits and Credits. > > > On Tue, Jun 7, 2011 at 7:39 PM, vishnu madiga <[email protected]> > wrote: > > find a combination of credits and debits which will sum out to zero in > > a given set of credit and debit values. > > It's not necessary to have a one to one match between a debit and > > credit. > > > > For example, the parent may lend $25 and $75 to its subsidiary and > > receive back 3 payments of $20, $40 and $40. > > The task is to match these entries in an account. This becomes taxing > > because multiple debits can be applied to > > multiple credits. In many cases there is more than one way to match > > the values. > > > > The goal is to develop a solution which will take a set of credits and > > debits and match as many debits to as > > many credits as possible. A test case could have up to 2,000 debits > > and credits. > > > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > [email protected]. > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > > -- > --Navneet > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
