alle Tupel einer Variation ermitteln

[oki]

Hi,

wenn jemand diesen Thread liest;

während ich mich durch die thematik schlage und versuche meine eigenen Schlüsse zu ziehen, muß ich auf jeden Fall erst mal Ordnung schaffen.

Also,

1. Bsp. von negaH.

Zitat:

CombiStrings(['A', 'B', 'C', 'D'], True);

Dies ist das Beispiel einer Permutation.
Ob nun die Permutation eine Teilmenge der Variation ist sei dahin gestellt. Mit Hilfe der hier genannten Funktion wird auf jeden Fall die Menge der Tupel einer Permutation abgebildet. Die Anzahl der gefundenen Tupel ist n! (Fakultät).

2. Bsp. von alzaimar:

Zitat von alzaimar:

Hier eine Möglichkeit:

Delphi-Quellcode:

Procedure Variation (Const s,q : String; i,k,n : Integer);
Var
  j : Integer;

Begin
  if k=0 Then
    Form1.memo1.Lines.Add(q) // Teilmenge gefunden, irgendwo muss sie ja hin
  else
    For j:=i+1 to n - k + 1 do
      Variation (s,q+s[j],j,k-1,n)
End;

Die Routine erstellt aus dem String s (Länge = n) alle k Teilmengen. Sei s='12345' und k=3, dann erfolgt der Aufruf mit:

Variation ('12345','',0,3,5)

Dies ist nicht die Variation, sondern die Kombination aller Elemente n zur k-ten Klasse.

Folgendes Bsp.:
Variation von 3 Elementen zur 2-ten Klasse: 12; 13; 21; 23; 31; 32 = 6 Tupel
Kombinationvon 3 Elementen zur 2-ten Klasse: 12; 13; 23 = 3 Tupel

Gut, ich hoffe, jetzt ist schon etwas Ordnung drin. Vielleicht finde ich jetzt mit den vorliegenden Ansätzen die Variation selber oder alzaimar ist schneller (will jemand wetten?)

Gruß oki

PS. Zwischenzeitlich ist nagaH's Post reingekommen.
Hallo und Dank auch dir. Kürzer heißt nicht immer besser ( wie zweideutig). Nee im ernst. Ich habe deinen Code auch noch nicht komplett durchgekaut und eine vorschnelle Wertung ist da unangebracht. Bei diesen ganzen Themen kommt man eh schnell in ziemlich hohe Zahlenbereiche. Da muß man gut abwägen welchen lösungsweg man nimmt. Gruß

[alzaimar]

Ach so: Dann schalte einen Permutator hinter jedes Element der 'Kombination', z.B. den hier (Der Code ist von Horst_H, glaub ich):

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;

Procedure Variation (Const s,q : String; i,k,n : Integer);
Var
  j : Integer;

Begin
  if k=0 Then
    For j:=1 to Fakultaet(k) do
      Form1.memo1.Lines.Add(NThPermutation (q,j)) // Teilmenge gefunden, irgendwo muss sie ja hin
  else
    For j:=i+1 to n - k + 1 do
      Variation (s,q+s[j],j,k-1,n)
End;

[negaH]

Hm, ich meine alzaimar's code müsste mit kleinen Änderungen auch deine Variationen erzeugen können.

Gruß Hagen

[alzaimar]

Zitat von negaH:

Hm, ich meine alzaimar's code müsste mit kleinen Änderungen auch deine Variationen erzeugen können.

Echt? Geht das nicht 1:1? Sind die Variationen nicht einfach die Permutationen der einzelnen Kombinationen?

[negaH]

Nein ich meinte doch das dein Source ohne den Aufruf von NtPermutation auskommen können muß.

So schwierig ist das do garnicht

1,2,3 haben wir und suchen alle 2'er Kombinationen ohne Wiederholung. Also ohne 11, 22, 33.

11
12
13

21
22
23

31
32
33

die 11,22 und 33 können wir ganz einfach filtern da ihr Index=Zählschleife den gleichen Wert haben wird.
Ergo rekusiv durch 123 durchgehen (n) und alle Kombinationen erzeugt die k Elemente aufweisen wobei der Index in unsere Lockuptabelle -> "123" nicht gleich sein darf. Im Grunde machst du das schon, nur musst du in der Rekusion eben den String "123" immer wieder bei 1 beginnen lassen.

Auf einen Delphi Code möchte ich mich mal nicht einlassen, zZ. könnte ich diesen nicht verifizieren da ich gerade mein Laptop neu installiere ;( Und bei sowas poste ich ungern einen Source der ungetestet ist

Gruß Hagen

[oki]

Hi,

ich hab jetzt mal den letzten Code von alzaimar getestet. Ergebnis für Variation und Kombination gleich.

Ich versteh im besonderen nicht, was die Funktion
Function NthPermutation (const aString : AnsiString; aCount : Integer) : AnsiString; genau macht. vorallem im code-bsp. fällt folgende Stelle auf:

Delphi-Quellcode:

  if k=0 Then
    For j:=1 to Fakultaet(k) do
      Form1.memo1.Lines.Add(NThPermutation (q,j)) // Teilmenge gefunden, irgendwo muss sie ja hin

Wenn K = 0, dann Fakultaet(k) auch immer 0. Dann ist die Schleife eigentlich auch überflüssig. Ich hab so den Eindruck das hat was mit der Fakultät auf die Klasse zu tun, denn

Variation = Kombination * Fakultät(Klasse) ergibt mathematisch die anzahl aller Variationen.

NaJa

Gruß oki

[marabu]

Hallo Leute,

jetzt nicht lachen, aber in den Anfangszeiten von Turbo Pascal hat mir ein blinder Kollege von seinem Hobby erzählt - einmal die Woche veröffentlichte die Wochenzeitung DIE ZEIT sieben Buchstaben, aus denen man möglichst viele sinnvolle Wörter bilden sollte. Wer die meisten Wörter einschickte, gewann 100 DM. So oder ähnlich war das.

Mit seinem damaligen Rechner und 4.7 MHz lies er ein Programm mehrere Tage laufen, welches ihm die einzelnen Variationen erzeugte, sortierte und gruppiert nach Länge auf seinem Nadeldrucker ausdruckte. Die Ausdrucke hat er dann mit seinen Speziallesegeräten untersucht und kurz vor Einsendeschluss stieg sein Puls erheblich an.

Ich habe ihm damals mit TP3 ein Programm geschrieben, welches die einzelnen Teilfunktionen stark beschleunigte. Variationen der sieben Buchstaben wurden durch eine kleine rekursive Prozedur gebildet, deren Zugriffe auf globale Variablen ich hier eliminiert habe:

Delphi-Quellcode:

procedure
  Variate (head, tail: String; varClass: Byte; s: TStringList);
var
  i: Integer;
  newHead, newTail: String;
begin
  for i := 1 to Length(tail) do
  begin
    newHead := head + tail[i];
    newTail := tail;
    Delete(newTail, i, 1);
    if (newTail = '') or (Length(newHead) = varClass)
      then s.Add(newHead)
      else Variate(newHead, newTail, varClass, s);
  end;
end;

Der Aufruf erfolgt dann so:

Delphi-Quellcode:

var
  s: TStrings;
begin
  s := TStringList.Create;
  Variate('', 'SURINAM', 4, s);
  // ...
end;

Getippt und nicht getestet, aber vielleicht hilft es ja ein wenig weiter.

Grüße vom marabu

[alzaimar]

Das ist mir natürlich peinlich, einfach so ungetesteten Code hier zu posten. Mein Zusatz mit 'NThPermuation', das übrigens alle Permutationen einer Zeichenkette bildet, hätte so lauten müssen:

Delphi-Quellcode:

if k=0 Then
  For j:=1 to Fakultaet(Length (q)) do
    Form1.memo1.Lines.Add(NThPermutation (q,j)) // Teilmenge gefunden, irgendwo muss sie ja hin

Dann werden von jeder Kombination alle Permutationen gebildet. Natürlich ist die ständige Berechnung von 'Length(q)' blödsinnig, aber das würde man auch noch hinbekommen.

Es geht aber noch einfacher:

Delphi-Quellcode:

Type
  TByteSet = Set Of Byte;

Procedure Variation (Const s,q : String; k,n : Integer; B : TByteSet);
Var
  j : Integer;

Begin
  if k=0 Then
    Form1.memo1.Lines.Add(q) // Teilmenge gefunden, irgendwo muss sie ja hin
  else
    For j:=1 to n do
      if not (j in B) then
        Variation (s, q + s[j], k - 1, n, B + [j])
End;

begin
  Variation ('123','',2,3,[]); // Alle 2-Tupel der Menge '123' (mit 3 Elementen)
end;

Statt nur die restlichen Elemente von S zu verwenden, nimmt man bei der Variation einfach alle bisher nicht verwendeten. Dazu verwende ich ein TByteset, das die bisher verwendeten Elemente (bzw. deren Position in S) speichert.

Anmerkung: Und wenn man n=k setzt, bekommt eine weitere Variation für Code, der alle Permutationen bildet.

[oki]

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