Die folgende Funktion berechnet rekursiv die Stirling-Zahlen erster Art. Diese werden zur Berechnung der Anzahl unterschiedlicher Permutationen mit n Elementen in r Zykeln verwendet (Mehr Info:
http://de.wikipedia.org/wiki/Stirling-Zahl)
Delphi-Quellcode:
function Stirling1(n, r: integer): integer;
begin
if ((n = 0) and (r = 0)) or (n = r) then
begin
Result := 1;
Exit;
end;
if ((n > 0) and (r = 0)) or ((n = 0) and (r > 0)) then
begin
Result := 0;
Exit;
end;
Result := Stirling1(n - 1, r - 1) + (n - 1) * Stirling1(n - 1, r);
end;
Die Stirling-Zahlen zweiter Art beschreiben die Anzahl Anzahl der unterschiedlichen Möglichkeiten aus einer Menge mit n Elementen r nichtleere, disjunkte Teilmengen zu bilden.
Delphi-Quellcode:
function Stirling2(n, r: integer): integer;
begin
if ((n = 0) and (r = 0)) or (n = r) then
begin
Result := 1;
Exit;
end;
if ((n > 0) and (r = 0)) or ((n = 0) and (r > 0)) then
begin
Result := 0;
Exit;
end;
Result := Stirling2(n-1,r-1)+r*Stirling2(n-1,r);
end;
Leider habe ich nur eine Definition der Stirling-Zahlen gefunden, die eine nicht-lineare Variante zur rekursiven Berechnung ermöglicht, sodass der Rechenaufwand mit großen Zahlen exponentiell steigt.
Stichwörter: Diskrete Strukturen Mengen Permutation Kombinatorik Rekursion
[edit=fkerber]Kleinen Fehler ausgebessert. Mfg, fkerber[/edit]