alle Tupel einer Variation ermitteln

[oki]

Hallo Leute,

irgentwo hängt es bei mir, aber mir fällt echt kein Weg ein.

Ich will alle Variationen einer Menke n zur k-ten Klasse ermitteln. Die anzahl dieser Variationen zu berechnen ist sicher nicht schwer. Dies erfolgt nach der Formel:

http://upload.wikimedia.org/math/1/d...0624e73dca.png

Nun möchte ich aber alle möglichen Einzelmengen ermitteln und speichern (Ort ist erst mal egal, kann Array, Object, List oder sonst was sein).

die Variation ist laut Wikipedia wie folgt definiert: Wikipedia Variation

Wie kann ich jetzt alle betreffenden Teilmengen (Tupel) ermitteln?

Dank im Voraus

oki

[Luckie]

Such mal hie rim Forum nach bruteforce.

[negaH]

http://www.delphipraxis.net/internal...ht=kombination

Delphi-Quellcode:

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

erzeugt dann eine Liste wie

Code:

A,B,C,D
A,B,D,C
A,C,B,D
A,C,D,B
A,D,B,C
A,D,C,B
B,A,C,D
B,A,D,C
B,C,A,D
B,C,D,A
B,D,A,C
B,D,C,A
C,A,B,D
C,A,D,B
C,B,A,D
C,B,D,A
C,D,A,B
C,D,B,A
D,A,B,C
D,A,C,B
D,B,A,C
D,B,C,A
D,C,A,B
D,C,B,A

Gruß Hagen

[oki]

Dank Lucki, Dank negaH!!

Das bringt mich nach vorne und den Rest bekomme ich dann hin.

Gruß oki

[oki]

Hi

Zitat:

Zitat von oki

... und den Rest bekomme ich dann hin.
Gruß oki

nicht ganz aufgepaßt und zu früh gefreut. :roll:

Ich benötige die Tupel einer Variation, nicht Kombination. :warn:

das sind zwar bedeutend weniger, aber stimmen muß es trotzdem. Hat da jemand noch eine Formel oder einen Algorithmus?

Der Verweis nach bruteforce war zwar schon die richtige Richtung, trifft aber nicht ganz (knapp daneben ist auch vorbei).

Gruß oki

[negaH]

http://de.wikipedia.org/wiki/Kombinatorik

lies dir das mal durch, dein obiger Link hat nichts mit Kombinatorik zu tuen.

Und eine Permutation ist auch eine Variation, allerdings eben von N Elementen auf K Plätzen, wobei N==K. Bei einer Variation ist also N >= K.

Mein Code sollte ohne weiteres abänderbar sein.

Gruß Hagen

[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:

Delphi-Quellcode:

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

[edit]Aufruf korrigiert. i ist Anfangs 0 (und nicht 1)[/edit]

[oki]

Hi,

@negaH: Hast recht! Ich war auf deinem Link bei Wikipedia und hatte nochmals Variation als Suchbegriff eingegeben. Beim thread schreiben und Umschalten hattte ich dann aus Versehen den falschen Link gesetzt.

Sich ist jede Permutation auch eine Variation, aber nicht jede Variation ist auch eine Permutation. Und ich brauche halt die Variation und nicht eine spezielle Form der Variation, hier Permutation. Trotzdem hilft mir das. Mir ist leider nur noch nicht aufgegangen, wo ich deinen Code ändern muß um eine Variation zu bekommen (Im funktionsaufruf die Klasse mit angeben ist natürlich obligatorisch).

@alzaimar: Ich hatte im stillen gehofft, dass du dich meldest. Bei meiner suche hier im forum ist mir schon aufgefallen, dass du hier wohl der Matheguru bist. Hat auch geklappt :zwinker: . Dank für die Hilfe. Ich bin erstaunt, wie kurz man das halten kann. Auf anhieb versteh ich den Code zwar nicht, aber ich teste ihn und stell dann später meine Fragen.

Dank und Gruß oki

[alzaimar]

Zitat:

Zitat von oki

@alzaimar... Matheguru

:shock: Nee. Algorithmen vielleicht, aber Mathe?

Zitat:

Zitat von oki

Auf anhieb versteh ich den Code zwar nicht...

Wir wollen k Elemente aus einem String extrahieren.
Gehen wir das ganze rekursiv an. Dann muss man die Aufgabenstellung so umformulieren, das ich eine Grundsituation habe, die ich mit einem Schritt weiter zur Lösung bringt. Daneben benötige ich eine Ausgangssituation sowie ein Abbruchkriterium.

Na gut, ich hab schon q Elemente extrahiert. Diese Elemente habe ich irgendwie aus den Stellen 1..i des Grundstrings genommen. Logisch, das ich nur noch die Elemente i+1 .. n für den Rest verwenden kann. Na gut, dann beppe ich einfach sukkessiv jeweils ein Element (nämlich die elemente i+1 .. n) an q ran und mache dann rekursiv weiter.

Gut, wie fangen wir an? Klar, q ist zunächst leer und ich habe also noch alle Elemente zur Verfügung, um die Teilmengen aufzubauen.

Wann hören wir auf? Auch klar, wenn in q genau k Elemente enthalten sind.

Natürlich hab ich einen kleinen Fehler im Aufruf eingebaut, der aber mittlerweile behoben ist.

[negaH]

nimm alzaimar code, dieser ist von der Lesbarkeit viel eleganter als meiner. Allerdings muß ich als Verteidung anführen das es bei meinem Codebeispiel auch darum ging ohne aufwendige Stringfunktionen -> s := s + t usw. auszukommen ;) Solche Operationen sind immer sehr langsam.

Gruß Hagen

[oki]

Hi,

wenn jemand diesen Thread liest; :oops:

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:

Delphi-Quellcode:

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:

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:

Delphi-Quellcode:

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 :zwinker: (will jemand wetten?)

Gruß oki

PS. Zwischenzeitlich ist nagaH's Post reingekommen.
Hallo und Dank auch dir. Kürzer heißt nicht immer besser ( :mrgreen: 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:

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. :cry:

Ich versteh im besonderen nicht, was die Funktion

Delphi-Quellcode:

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 :gruebel:

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 :zwinker: 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 :roll: ).

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