Blog

Das Leben schreibt die besten Geschichten, heißt es. Und wenn die Moral dieser Geschichte auch noch auf das eigene Berufsleben passt, warum nicht erzählen? Warum es also leichter ist, sich vorher zu überlegen, was man tut, und welche Rolle ein neugieriger Sohn, Mathematik und Permutationen dabei spielen, erfahren Sie in folgendem Beitrag.

Sobald mein Sohn Lorenz von der Schule nach Hause kommt, beginnt er selbstständig mit seinen Hausübungen. Dabei setzt er sich an einen etwa 100 Jahre alten Schreibtisch mit Samt-Auflage, auf dem schon mein Großvater arbeitete. Unlängst fragte mich Lorenz, auf wie viele verschiedene Arten man die Laden des Schreibtisches vertauschen kann.

Dazu muss man wissen: Der Schreibtisch hat 9 Laden, die alle die gleiche Größe aufweisen. Somit können alle Laden untereinander beliebig vertauscht werden. Es stehen also 9 Plätze für 9 Laden zur Verfügung. Für die Mathematiker:innen unter uns ist es wohl ein leichtes hier die entsprechende Lösung zu finden. Aber erstens sind wir nicht alle mit Archimedischen oder Keplerschen Fähigkeiten ausgestattet und zweitens ist der Weg zur Lösung je bekanntlich und sprichwörtlich das Ziel. So auch hier.

3 Laden, 3 Schubladen und ein paar Fragen

Um das Problem in einer leichteren Variante zu veranschaulichen, geben wir uns vorerst mit 3 Laden zufrieden, um es später auf den Schreibtisch mit den 9 Laden zu übertagen.

Wir haben also 3 Laden mit den Bezeichnungen A, B und C sowie 3 Plätze mit den Bezeichnungen 1, 2 und 3. Zuerst entfernen wir alle Laden aus dem Schreibtisch. Wenn wir nun die Lade A in den Schreibtisch geben wollen, sind noch alle 3 Plätze frei. Es gibt also 3 Möglichkeiten für die Platzierung der Lade. Anschließend, wenn wir die Lade B in den Schreibtisch stecken möchten, bleiben uns nur mehr 2 Plätze übrig, da ja ein Platz bereits durch die Lade A belegt ist. Schließlich gibt es für die Lade C nur mehr einen Platz. Diese Methodik lässt sich ein paar Mal anwenden – je nachdem, an welchem Platz wir mit Lade A starten. Die nachstehende Tabelle listet alle Möglichkeiten auf:

Mathematisch gesehen spricht man hier von Permutationen, also Vertauschungen. Und die Anzahl der möglichen Vertauschungen für 3 Laden errechnet sich wie folgt: 3*2*1 = 6. Alternativ kann man auch einfach 3! schreiben (gesprochen: 3 faktorielle).

Nun legen wir das Problem auf einen Schreibtisch mit 4 Laden (A, B, C, D) um: Für die Lade A bleiben uns also 4 Plätze, für die Lade B bleiben 3 Plätze, usw. Leicht ersichtlich ist nun also, dass wir die Anzahl mittels 4*3*2*1 = 4! = 24 berechnen können. Für den Schreibtisch mit 9 Laden ergeben sich also 362.880 mögliche Vertauschungen. Und gleich, wie viele Schubladen es auch geben mag, diese Systematik lässt sich für jeden noch so großen Schreibtisch anwenden. Oder anders gesagt: Für eine beliebige Anzahl ‚n‘ an Laden kann man die Anzahl der Vertauschungen mittels n! berechnen.

Nachstehend finden Sie noch eine Tabelle, die Ihnen die Anzahl der Vertauschungen in Abhängigkeit der Schubladen in der Übersicht zeigt:

Quelle: Wolfram Alpha

Alles klar – oder doch nicht?

So weit, so gut, so klar. Ich habe mir den Spaß erlaubt, den Heap-Algorithmus, der zum Auflisten aller Permutationen verwendet werden kann, mit ABAP auf einem unserer Testsystem zu implementieren. Anschließend habe ich mit dem Programm alle Vertauschungen für 11 Schubladen ermitteln lassen. Dabei habe ich aber die einzelnen Vertauschungen nicht ausgegeben und trotzdem hat es ca. 1,5 Minuten gedauert alle zu ermitteln.

Zugegeben, diesen Weg einzuschlagen, ist praktisch sinnlos, denn die Anzahl der Vertauschungen ist schnell ausgerechnet. Wenn man Vertauschungen zudem gar nicht visualisiert, hat das Programm keinen echten Mehrwert. Was das Programm aber sehr schön zeigt, ist (und nun kommen wir langsam der Moral der Geschichte näher), dass es auch für eine kleine Eingabemenge zu hohen Laufzeiten kommen kann.

Wichtig ist, sich im Klaren zu sein, dass nicht alle Problemstellungen einfach bzw. schnell zu lösen sind. Bevor man also versucht ein Problem zu lösen oder einfach mal wild drauf los programmiert, sollte man zuerst das Problem bzw. die Aufgabe analysieren und einschätzen, ob dies überhaupt sinnvoll möglich oder lösbar ist. Das so oft in der Praxis angewendete Lösungsverfahren „alle Möglichkeiten auflisten und dann die richtige daraus suchen“ ist in den wenigsten Fällen ideal. Besser wäre es die Lösung nach gezielten Verfahren zu konstruieren.

Von Mathe ins (Berufs-)Leben

Und damit wären wir wieder bei unserem Schreibtisch: Egal, wie man es dreht und wendet, und egal, welchen Algorithmus man in diesem Fall wählt, die Anzahl der Permutationen wird natürlich nicht weniger. In vielen Fällen aber reicht eine einzige Lösung für ein Problem (z.B. nur eine Vertauschung). Dass es daneben noch weitere, zahlreiche andere Lösungen gibt (alle Vertauschungen), ist gut, aber nicht notwendig.  

Das Auflisten aller möglichen Vertauschungen zählt zur Kombinatorik und diese ist wiederum ein Teil der diskreten Mathematik. Die diskrete Mathematik umfasst sehr viele Gebiete der Informatik und der Algorithmik, und darin kann ein grundlegendes Basiswissen in unserem Beruf nicht schaden. Nicht für Sie, nicht für mich, nicht für meinen Sohn. Wie er mich gefragt hat, können Sie mich auch fragen, wenn Sie mehr darüber wissen wollen. Oder wenn Sie wissen wollen, wie der Schreibtisch mit seinen Schubladen den Weg in unsere vier Wände gefunden hat. Aber das ist wieder eine ganz andere Geschichte.