programmieren - wie mach ich das (Ansatz)

[Tommi]

Hallo!
Sitzt jetzt schon seit längerem und komm nicht so recht dahinter wie ich das lösen soll....
also ich will ein Programm schreiben, dass mir alle verschiedenen Möglichkeiten ausgeben kann..
zb. für 3 also 123:

123
132
213
231
312
321

und das für n viele stellen
Mir gehts jetzt gar nicht um das fertige script, sondern um einen Lösungsansatz, schreiben kann ichs dann glaub ich schon selber....

vielleicht hat jemand von euch einen geistesblitz

Mfg und schönen Abend noch Tommi

 

[crumble]

Das geht über die Erzeugung einer Permutation.
(klass. Code)

procedure visit(k: integer);
 var t: integer;
 begin
 id:=id+1;val[k]:=id;
 if id=V then writeperm;
 for t:=1 to V do
  if val[t]=0 then visit(t);
 id:=id-1; val[k]:=0
 end;

Die Prozedur writeperm bewirkt einfach die Ausgabe der Elemente des Feldes val. Dies erfolgt jedesmal, wenn id=V (Pfadlänge des Graphen) gilt, was der Entdeckung eines vollständigen Pfades im Graph entspricht. (Das Prog. kann noch etwas verbessert werden, indem man die for-Schleife weglässt, wenn id=V gilt, da in diesem Falle bekannt ist, dass alle Einträge in val von null verschieden sind.) Um alle Permutationen der ganzen Zahlen von 1 bis N auszugeben, ruft man diese Prozedur mit visit(0) auf, wobei id mit -1 und das Feld val mit 0 initialisiert wird. Dies entspricht der Einführung eines Pseudo-Knotens in dem vollständigen Graph und dem Prüfen aller Pfade im Graph, die mit Knoten 0 beginnen. Wenn die Prozedur in dieser Weise für N=3 aufgerufen wird, erzeugt sie deine Ausgabe. (bis auf die Reihenfolge )

 

[Tommi]

hmm so ganz blick ich da ned durch....

was meinst du mit graph? und entdeckung eines graphen usw?

 

[crumble]

Es handelt sich dabei um sog. "Erschöpfendes Suchen", d.h. du suchst dir sämtliche (alternative) Wege, die zum Ziel führen:

        root
      /    |     \
     1     2     3
   /  | \  /|\    /|   \
  1   2 3  12 3   ...

jede Lsg. wird mit dem Durchlauf durch einen Graphen (von root bis zum untersten Element, dem Blatt) ermittelt. (Teilung=Knoten)
man steigt zum Bsp immer soweit links abwärts, wie möglich bzw. erfordert. geht es nicht weiter nach links unten, geht man zum letzten knoten zurück (backtracking), geht an diesem knoten nach rechts und beginnt wieder von vorne mit dem links-absteigen.

Dieses Verfahren würde aber auch zB 113 liefern, also müssen doppelte Zahlen ausgeschlossen werden, welches durch das "Merken" (+ Vergleich) der bereits ermittelten Zahl(en) erfolgt:

           root
        /     |    \
      1       2     3
    /  |      /\    / \
    2  3      1 3   1  2
    |  |       ...
    3  2

Also wär 123 ein möglicher Graph, der sozusagen die Lösung repräsentiert.

 

[carmin]

Neben der von crumble skizzierten rekursiven Variante gibts auch noch folgende. Die aber setzt voraus, dass die Elemente miteinander vergleichbar und die Permutationen damit in eine lexikalische Reihenfolge zu bringen sind. Dann startet man mit der "kleinsten" Permutation (123...n) und kommt von einer zur nächsten, indem man von rechts nach links die erste Stelle i sucht, die kleiner ist als die nachfolgende, ersetzt das Element an Stelle i durch das nächstgrößere irgendwo rechts davon und kehrt die Reihenfolge der Elemente (i+1)...n um.

Oder als Code:

  boolean nextPermutation(int[] v)
  {
    int i = v.length - 1;

    while (true) {
      if (i <= 0) {
        reverse(v, 0, v.length);
        return false;
      }

      int succ = i;
      --i;
      if (v[i] < v[succ]) {
        int j = v.length;
        while (v[i] >= v[--j]);
        swap(v, i, j);
        reverse(v, succ, v.length);
        return true;
      }
    }
  }

Hier vertauscht swap(v, i, j) die Elemente i und j in v, und reverse(v, i, j) kehrt die Reihenfolge der Elemente i ... (j-1) in v um.

Verwendet wird diese Funktion etwa so:

    int[] p = { 1, 2, 3, ..., n };
    do {
      print(p);
    } while (nextPermutation(p));

Hoffe, das war noch ne hilfreiche Anmerkung ...
Greetz