Alle Permutationen von n Aufträgen berechnen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo.

Bin gerade dabei mich in Wirtschaftsinformatik einzuarbeiten und hadere gerade mit einer Aufgabe rum die mir ziemliches Kopfzerbrechen bereitet.
Scheint eigentlich eine sehr einfache Aufgabe zu sein, leider habe ich keine Ahnung wie ich vorgehen soll, bin halt kein Programmierer oder Mathematiker. Würde gerne wissen wie man so etwas löst:

Sie wollen ein Programm schreiben, welches Ihnen in einer internen Tabelle alle Permutationen (Reihenfolgen) von n Aufträgen berechnet (n=8).

Welches Datenmodell benutzen Sie?
Wie gehen Sie beim Algorithmus vor?

Bsp. Sie haben 5 Aufträge:
A1, A2, A3, A4, A5

Es gibt folgende Permutaionen:

A1, A2, A3, A4, A5
A1, A2, A3, A5, A4
usw.

Währe sehr nett wenn mir jemand helfen könnte.
Vielen Dank für im voraus!

#2

Hallo mgen,

so schwer, wie die Zeitdauer bis zu meiner Antwort vermuten lässt, ist das Problem auch wieder nicht.
Es gibt ziemlich verschiedene Ansätze zur Lösung, zwei Ideen hier als Startpunkt; wenn die Ergebnisse in einem Array abgelegt werden sollen, ist das n ohnehin ziemlich beschränkt. Ich würde jede Permutation als Zeichenkette ablegen und jeden Auftrag als ein Zeichen. Bei n=8 reichen die Ziffern, bei höheren Werte kann man bei Buchstaben borgen.

Der direkteste Weg ist eine Rekursion über eine Funktion, die zwei Operanden hat: den bereits festgelegten Anfang der Folge und den Vorrat von Restaufträgen.
Man fängt also mit ("", „12345678“) an, macht dann ein Laufschleife über die Restaufträge (welcher als nächstes dran kommt) und ruft dieselbe Routine wieder auf („1“, „2345678“), also ausgewähltes Element an die festgelegte Folge anhängen und aus dem Restvorrat entfernen. Wenn kein Restauftrag mehr da ist, hat man ein Ergebnis, das man in das Array schreibt und kann die Rekursion beenden. Hinterher kann prüfen, ob man alle n! Permutationen erwischt hat.

Man kann auch die primitive Reihenfolge „1…8“ in das Array schreiben, und dann mit verschiedenen Methoden zusätzliche Reihenfolgen generieren, indem man eine bekannte Reihenfolge aus dem Array auswählt und zwei Positionen darin miteinander vertauscht. Wenn man dabei nicht sehr systematisch vorgeht, muss man sicherstellen, dass eine so erzeugte Folge nicht bereits bekannt ist.

Grüße, guidot

#3

Danke guidot für die ausführliche Antwort!

Gruß mgen