Die Anzahl der Permutationen aus n Elementen ist n!. Dies ist durch die folgende Überlegung, genannt mathematische Induktion, einleuchtend. Angenommen, wir haben alle Permutationen aus n-1 Elementen. Daraus erzeugen wir die Permutationen aus n Elementen, indem wir die Permutationen aus n-1 Elementen n-mal kopieren. Das n-te Element wird nun in der ersten Kopie vor das erste Element geschoben, in der zweiten vor das zweite, usw.; in der n-1-sten Kopie vor das n-1-ste (also das letzte) Element, schließlich in der n-te Kopie nach das letzte Element. Wenn die Anzahl der Permutationen aus n-1 Elementen Pn-1 war, dann erhalten wir auf diese Weise n.Pn-1 verschiedene Permutationen. Für n=1 ist diese Anzahl 1, also ist Pn = n!.
Wir entwickeln nun eine Paketschablone für die rekursive Berechnung von Permutationen. Die Schnittstelle der Schablone ist:
generic -- Permut.ada type TBasis is private; package GPermutationen is -- Permutationen rekursiv berechnen type TReihung is array (Positive range <>) of TBasis; -- TReihung'First = 1 type TPermutationen is array (Positive range <>, Positive range <>) of TBasis; -- TPermutationen'Range(1) = 1 .. Fak (TReihung'Last); TPermutationen'Range(2) = TReihung'Range function Permutationen (Reihung: TReihung) return TPermutationen; -- liefert alle Permutationen von Reihung function Fak (N: Positive) return Positive; -- Hilfsfunktion Fakultät end GPermutationen;
In der rekursiven Funktion Permutationen werden wir eine lokale Reihung Temp: constant TPermutationen (1 .. Fak (Reihung'Length-1), 1 .. Reihung'Length-1) := Permutationen (Reihung (1 .. Reihung'Length-1)); anlegen, die die Permutationen aus n-1 Elementen enthält. Sie sollen diese in das Ergebnis (ebenfalls eine lokale zweidimensionale Reihung der Größe n! x n, ) n-mal kopieren und das letzte Element Reihung (Reihung'Length) an die 1-ste, 2-te, ... n-te Stelle einschieben. Eine geschickte Manipulation der Indizes ist hier der Schlüssel für eine elegante Lösung.
package body GPermutationen is -- Idee: Die Permutationen aus n können aus den Permutationenutationen aus n-1 berechnet werden, -- indem das n-te Glied auf die i-te Stelle (für i=1 .. n) aller Permutationenutationen aus n-1 eingeschoben wird.
function Fak (N: Positive) return Positive is begin return N * Fak (N-1); -- raises Constraint_Error wenn N-1 not in Positive exception when Constraint_Error => return 1; end Fak;
function Permutationen (Reihung: TReihung) return TPermutationen is Dimension: constant Positive := Reihung'Length; Fak_Dimension: constant Positive := Fak (Dimension); -- Anzahl der Permutationenutationen aus N ist N! Ergebnis: TPermutationen (1 .. Fak_Dimension, 1 .. Dimension); -- Dimension! Zeilen begin if Reihung'First /= 1 then -- Vorschrift pruefen raise Constraint_Error; end if;
if Dimension = 1 then Ergebnis (1, 1) := Reihung (1); else
declare Temp: TPermutationen (1 .. Fak (Dimension - 1), 1 .. Dimension - 1) := Permutationen (Reihung (1 .. Dimension - 1)); -- rekursiv Permutationen aus Dimension-1 Erg_Zeile: Positive range Ergebnis'Range(1) := Ergebnis'First(1); begin -- nun wird Temp Dimension-mal kopiert; das letzte Element Reihung (Dimension) wird jedesmal dazwischengeschoben for Erg_Spalte in Ergebnis'Range(2) loop -- in jeder Zeile von Ergebnis wird das Element Reihung (Dimension) auf die I-te Stelle eingeschoben for Temp_Zeile in Temp'Range(1) loop for Temp_Spalte in Temp'Range(2) loop -- Spalten in Temp: Temp (J, K) kopieren if Temp_Spalte < Erg_Spalte then -- Spaltenvergleich: vor der I-ten Spalte normal, ab der I-ten Spalte verschoben kopieren Ergebnis (Erg_Zeile, Temp_Spalte) := Temp (Temp_Zeile, Temp_Spalte); -- normal kopieren else Ergebnis (Erg_Zeile, Temp_Spalte+1) := Temp (Temp_Zeile, Temp_Spalte); -- verschoben kopieren end if; end loop; -- Temp_Spalte
Ergebnis (Erg_Zeile, Erg_Spalte) := Reihung (Dimension); -- letztes Element einschieben begin Erg_Zeile := Erg_Zeile + 1; exception -- das letzte Mal when Constraint_Error => null; -- check Erg_Zeile = Dimension; end; -- exception für Erg_Zeile end loop; -- Temp_Zeile end loop; -- Erg_Spalte end; -- declare Temp end if; -- Dimension = 1 return Ergebnis; end Permutationen; end GPermutationen;
Diese Schablone wird im nächsten Stapeltestprogramm ausgeprägt:
with GPermutationen, Text_IO; procedure Stapel_Permutation is type T is new Character; -- austauschbar package MPermutationen is new GPermutationen (T); Reihung: constant MPermutationen.TReihung := "abcdef"; -- austauschbar Permutationen: constant MPermutationen.TPermutationen (1 .. MPermutationen.Fak (Reihung'Last), Reihung'Range) := MPermutationen.Permutationen (Reihung);
begin
Text_IO.Put ("Alle Permutationen von ");
for I in Reihung'Range loop
Text_IO.Put (T'Image (Reihung (I)) & " ");
end loop;
Text_IO.Put_Line ("sind:");
for I in Permutationen'Range(1) loop
for J in Permutationen'Range(2) loop
Text_IO.Put (T'Image (Permutationen (I, J)) & " ");
end loop;
Text_IO.New_Line;
end loop;
end Stapel_Permutation;
Ein Dialogtestprogramm ist:
with GPermutationen, Text_IO; procedure Dialog_Permutation is type T is new Integer; -- austauschbar package MPermutationen is new GPermutationen (T); package Pos_IO is new Text_IO.Integer_IO (Positive); Dimension: Positive;
begin
Text_IO.Put_Line ("Permutationen werden rekursiv berechnet.");
Text_IO.Put ("Aus wievielen Elementen? (positive ganze Zahl):");
Pos_IO.Get (Dimension);
declare
Reihung: MPermutationen.TReihung (1 .. Dimension);
Permutationen: MPermutationen.TPermutationen (1 .. MPermutationen.Fak (Reihung'Last), Reihung'Range);
begin
Text_IO.Put ("Alle Permutationen von ");
for I in Reihung'Range loop
Reihung (I) := T (I);
Text_IO.Put (T'Image (Reihung (I)) & " ");
end loop;
Text_IO.Put_Line ("sind:");
Permutationen := MPermutationen.Permutationen (Reihung);
for I in Permutationen'Range(1) loop
for J in Permutationen'Range(2) loop
Text_IO.Put (T'Image (Permutationen (I, J)) & " ");
end loop;
Text_IO.New_Line;
end loop;
end;
end Dialog_Permutation;
Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de
Leitseite des Autors