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

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 von oki:

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

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

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

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:

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 . 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 von oki:

@alzaimar... Matheguru

Nee. Algorithmen vielleicht, aber Mathe?

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