Version: SVN HEAD (using KDE 4.3.5) OS: Linux Installed from: openSUSE RPMs Source of this can be find on http://forum.kde.org/viewtopic.php?f=69&t=86137 I think that an automatic matching of the transactions that have to be cleared could be useful too, for example : I have 20 transactions in my KMyMoney that have been entered and not cleared. Only 15 of these transactions are on my bank statement. I enter the final number of my bank statement on the Reconciliation Wizard. KMyMoney may look for a combination of the 20 transaction that match the final number. Usually as the numbers are quite different it find only one combination, if so KMyMoney tell me : "If I clear those 15 transactions, your reconciliation is balanced. OK ?". If there are no combination possible it could tell me so, I will have to find the transactions I forget. If there are more than one combination, I will have to choose it myself. I know that combination problems aren't linear, so maybe the algorithm isn't easy to find (or effective), but such a feature could be really useful !
The first algorithm that I thought of when reading the requirements has a really big performance issue - it's execution time is O(2^N) where N is the number of possible transactions in the reconciliation period. This means that execution time doubles at each extra transaction in the reconciliation period. At let's say 20 transactions this could already take a while. The algorithm sounds something like this: "Generate the sum of all combination of numbers (the amount of transactions) until the target sum is obtained; if the target sum is not obtained than the automatic matching algorithm failed." We could gain some improvement from the fact that we already know the target sum so we could come up with an heuristic algorithm.
I think that the http://en.wikipedia.org/wiki/Subset_sum_problem is the same problem that we have.
I've tested an implementation of this algorithm http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm it seems to very good performance (I've tested it with 22 numbers so far). I'll implement this feature using this algorithm.
SVN commit 1127345 by conet: BUG: 228492 This is an initial implementation of the 'Automatic reconciliation' feature. It could still need optimizations but it's usable in it's current state and I think we'll manage to polish the rough edges until the next release. I've added a setting to enable the feature in the 'Register settings' page under the 'Data entry' tab since in the 'General settings' page the wasn't any room for another check-mark. M +13 -0 dialogs/settings/ksettingsregisterdecl.ui M +155 -0 kmymoney.cpp M +4 -0 kmymoney.kcfg WebSVN link: http://websvn.kde.org/?view=rev&revision=1127345