Suche in Buchhaltungsdaten, wer setzt mich auf die Schiene?

[MaxMurdoch]

Hallo Team,
ich fummle seit Wochen an einem Problem, zu dem mir selbst Oberstufenmathe nicht mehr reicht. Ist auch 40 Jahre her
Für das Problem unten bin ich mit "auf die Schiene setzen" bis hin zu "fertiger Lösung" zufrieden:

Ich suche in n Buchhaltungsbelegen oft nach allen Kombinationen von n, die in Summe einen vorgegebenen Wert x ergeben.
Aktuell hab ich nen simplen Algorithmus "DPA" (gefunden und genutzt), der mit positiven Ganzzahlen für wenige n ein Array aufpumpt.
Aber: mein DataFrame hat in der Wertespalte Fließkommawerte mit Vorzeichen. Zudem kann jedes Element n einen bereits vorhandenen Wert erneut haben.
Das packt der Algo nicht.

Also hab ich, hier mal als Liste, so etwas: [15.05, 31.02, 0.01, 0.02, -9.88, 15.05, -1.00, 13.13, 1.03, 0.01]
und suche nun die Mengen der Elemente n, die in Summe z.B. 0.03 ergeben. Sollte im Ergebnis führen zu:
[0.01, 0.02] (zweimal wegen 0.01)
[-1.00, 1.02, 0.01] (zweimal wegen 0.01)

Ist da in den Mathe-Libraries was verfügbar? Kann ich die Daten eventuell transformieren? Ich find nichts Brauchbares...

[pillmuncher]

Du könntest zuerst die Potenzmenge bilden, dann jede er erhaltenen Teilmengen aufsummieren und die Summe dann als Schlüssel in einem dict auf eine Liste von Teilengen abbilden. Das können mehrere sein, denn es könnte ja verschiedene Teilmengen geben, die dieselbe Summe haben. Etwa so:

Code: Alles auswählen

from collections import defaultdict
from itertools import chain, combinations
from pprint import pprint


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


def main():
    items = [15.05, 31.02, 0.01, 0.02, -9.88, 15.05, -1.00, 13.13, 1.03, 0.01]
    sets = powerset(items)
    sums = defaultdict(list)
    for each in sets:
        sums[sum(each)].append(each)
    pprint(sums.keys())


if __name__ == "__main__":
    main()

Wenn du dir das Ergebnis anschaust, dann wirst du sehen, dass es keine gute Idee ist, Geldbeträge in IEEE 754 floating point zu repräsentieren. Normalerweise speichert man Geldbeträge in Cents ab und rechnet das dann für die Darstellung in Euro um, oder man verwendet decimal.Decimal. Ich würde der Einfachheit wegen ersteres vorschlagen.

Auch bedenken solltest du, dass die Pontenzmenge exponentiell wächst mit steigender Kardinalität der zugrunde liegenden Menge. Die Formel ist 2^n bei n == len(items).

[MaxMurdoch]

Okay, das versuch ich mal nachzuvollziehen. Die Potenzmenge begrenzt natürlich das Machbare. Dazu werd ich die Belege flöhen.
Das mit den Cents ist natürlich richtig. Hatte ich schon bedacht, aber im Text nicht klar wiedergegeben
Na, mal sehen, was mich der Debugger Neues lehrt. Danke Pille

Soo: phantastisch. Genau das bringt's. Memory management für große Belegmengen muß halt her. Ich könnte ja diejenigen abgearbeiteten Dictionary-Elemente löschen, die die Zielsumme nicht bilden. Aber einmal muß es halt komplett aufgebaut werden. Vielleicht bringt der Wechsel auf Integer mit Vorzeichen Vorteile beim Speicher. Da bin ich zu weit weg von den Tiefen der Abbildung im System. Mal noch die Spezialfälle austesten ...

[pillmuncher]

Hier mit ohne extra eine Datenstruktur aufzubauen:

Code: Alles auswählen

from itertools import chain, combinations
from functools import partial
from pprint import pprint


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


def select_by_sum(num, items):
    return num == sum(items)


def main():
    items = [15.05, 31.02, 0.01, 0.02, -9.88, 15.05, -1.00, 13.13, 1.03, 0.01]
    pprint(list(filter(partial(select_by_sum, 18.3), powerset(items))))


if __name__ == "__main__":
    main()

Ergebnis:

Code: Alles auswählen

[(15.05, -9.88, 13.13), (-9.88, 15.05, 13.13)]