Hi Leute,
erst mal Dank für die rege Teilnahme. Auch wenn dieser thread nicht umfassend alle Möglichkeiten der Kombinatorik enthält, so wurde hier jedoch der wesentliche Teil zusammengetragen. Ich denke, dass hier erst einmal keiner absoluten Wert auf Vollständigkeit legt.
Da die Begriffswelt zwischenzeitlich etwas durcheinander geraten war, möchte ich hier für alle die diesen Thread später lesen die Ergebnisse noch einmal zusammen fassen.
In der Kombinatorik wird in der Regel die Frage beantwortet, wie viele Lösungen von Reihen für eine bestimmte Anzahl von Elementen unter den verschiedensten Annahmen existieren. Die wesentlichen Formen sind:
1. Die Permutation
2. Die Variation
3. Die Kombination
diese Themen sind recht gut bei Wikipedia unter folgendem Link beschrieben:
Wikipedia Kombinatorik
Nun ist es aus den verschiedensten Gründen sicher auch mal notwendig sowohl die Anzahl aller möglichen Tupen, wie auch die Menge zu berechnen.
Für die Anzahl erschien das relativ einfach, für die Menge eher weniger (zumindest mir
).
Hier möchte ich jetzt das Ergebnis noch einmal zusammen fassen, um vor allem Verwechslungen zu vermeiden.
Berechnung der Anzahl der Tupel
Permutation
Delphi-Quellcode:
Function Fakultaet(Elemente : Integer) : Int64;
var Counter : Integer;
begin
Result := 1;
For counter := 1 to Elemente do
Result := Result * Counter;
end;
Variation
Bei der Variation ist es von Vorteil nicht mit den Fakultäten zu rechnen. Hier stößt man schnell an die Grenzen. die Zwischenergebnisse sind dann immer erheblich größer als das Endergebnis.
Delphi-Quellcode:
Function Variation(Elemente, Klasse : Integer) : Int64;
var Counter : Integer;
begin
Result := 1;
// ohne Wiederholungen
For Counter := Elemente downto Elemente - Klasse + 1 do
Result := Result * Counter;
end;
Kombination
Für die Berechnung der Kombination gilt das gleiche an Bemerkungen wie für die Variation.
Delphi-Quellcode:
Function Kombination(Elemente, Klasse : Integer) : Int64;
begin
// ohne Wiederholungen
Result := Trunc(Variation(Elemente, Klasse, False) / Fakultaet(Klasse));
end;
Erstellen der Ergebnismengen
Hierbei ist es sehr vorteilhaft, dass sich die Ergebnismenge der Permutation als Untermenge der Variation für einen speziellen Fall der Parameter ergibt.
Permutation
Verwendung der Methode für die Variation mit dem Aufruf für K = N (Anzahl der Elemente = Klasse)
Variation
Delphi-Quellcode:
Procedure TupelVariation (Const s,q : String; i,k,n : Integer);
Var
j : Integer;
Begin
if k=0 Then
For j:=1 to Fakultaet(Length (q)) do
memo1.Lines.Add(NThPermutation (q,j)) // Teilmenge gefunden, irgendwo muss sie ja hin
else
For j:=i+1 to n - k + 1 do
TupelVariation (s,q+s[j],j,k-1,n)
End;
in dieser Methode wird die Bildung der Tupel der Permutationen benötigt, die hier wie im Thread benannt von Horst_H genommen wurde:
Delphi-Quellcode:
Function NthPermutation (const aString : AnsiString; aCount : Integer) : AnsiString;
Var
pos, i, n : Cardinal;
chTemp : char;
Begin
n := Length(aString);
result := aString;
for i := n downto 2 do
begin
pos := acount mod i +1;
//switch
chTemp := result[i];
result[i] := result[Pos];
result[Pos] := chTemp;
acount := acount div i;
End;
End;
Kombination
Delphi-Quellcode:
procedure TupelKombination(const s, q: String; i, k, n: Integer);
Var
j : Integer;
begin
if k=0 Then
memo1.Lines.Add(q) // Teilmenge gefunden, irgendwo muss sie ja hin
else
For j:=i+1 to n - k + 1 do
TupelKombination(s,q+s[j],j,k-1,n)
end;
Meine Zusammenfassung soll hier nicht den Anspruch der Vollständigkeit erheben. Da in den einzelnen Beiträgen die Begriffswelt (auch in den Methodenbezeichnern) etwas durcheinander geraten ist, habe ich diese zusammenfassung geschrieben. Ich habe hier auch alzamair's Code verwendet, weil somit ein relativ einheitlicher Ansatz für alle dargestellten Lösungen gezeigt werden kann. Er ist keine Wertung gegenüber den aufgeführten Code's aller anderen.
Hier möchte ich auch auf marabus Ansatz mit der Ergebnisrückgabe in einer Stingliste für die Tupel hinweisen. Nicht jedem ist die vordergründige Ausgabe in einem visuellen Element genehm.
Noch mals dank für die hilfe,
Gruß oki