Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Geordnete Auswahl als Liste ermitteln
ub60 - Mi 29.01.20 20:22
Titel: Geordnete Auswahl als Liste ermitteln
Hallo miteinander,
ich möchte von einer bestimmten Menge von Elementen eine bestimmte Anzahl entnehmen (ohne zurücklegen) und mir alle Möglichkeiten als Liste ausgeben lassen.
Um das zu verdeutlichen, ein kleines Beispiel:
Ich habe die 6 Buchstaben ABCDEF und suche alle Möglichkeiten, genau 3 Buchstaben zu wählen (geordnet). Ich würde also die folgende Liste erwarten:
---
ABC
ABD
ABE
ABF
ACD
ACE
ACF
ADE
ADF
AEF
BCD
BCE
BCF
BDE
BDF
BEF
CDE
CDF
CEF
DEF
---
Für kleinere Mengen geht das ja mit brute force, aber für größere Zahlen (etwa 5 Buchstaben aus 26) ist brute force nicht machbar.
Meine Idee für eine "normale rekursive Anordnung" sieht so aus:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| procedure ErmittleAnordnungsListe(Liste: TStringList; Ausgabe, Eingabe: String); var i : Integer; KopieAusgabe, KopieEingabe : String; begin for i:=1 to Length(Eingabe) do begin KopieAusgabe:=Ausgabe; KopieEingabe:=Eingabe; KopieAusgabe:=Ausgabe+Eingabe[i]; Delete(KopieEingabe,i,1); if KopieEingabe='' then Liste.Add(KopieAusgabe) else ErmittleAnordnungsListe(Liste, KopieAusgabe, KopieEingabe); end; end; |
Aufruf z.B. mit
Delphi-Quelltext
1:
| ErmittleAnordnungsListe(Liste, '', 'ABCD'); |
Hier würde mir die Liste aller Anordnungen der 4 Buchstaben ausgegeben.
Tja, und so etwas ähnliches suche ich nun für mein oben angegebenes Problem.
Vielen Dank schon mal!
ub60
Gausi - Mi 29.01.20 21:40
Das fand ich jetzt ne nette kleine Übung. Mein Ansatz:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| procedure GenerateList(Target: TStrings; Source: String; IndexS: Integer; lMax: Integer; currentEntry: String); var i: Integer; newEntry: String; begin for i := IndexS to (Length(Source) - (lMax - Length(currentEntry)) + 1 ) do begin newEntry := currentEntry + Source[i]; if Length(newEntry) = lMax then Target.Add(newEntry) else GenerateList(Target, Source, i + 1, lMax, newEntry); end; end; |
Aufruf besser über eine temporäre Stingliste, nicht direkt Lines von einer Memo (dauert sonst
erheblich länger)), also z.B.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| procedure TForm1.Button1Click(Sender: TObject); var s: String; sl: TStringList; begin Memo1.Lines.Clear; s := ''; sl := TStringList.Create; try GenerateList(sl, Edit1.Text, 1, Spinedit1.Value, s); Memo1.Lines.Assign(sl); finally sl.Free; end; end; |
Dauer bei 5 aus 26 (65780 Möglichkeiten): knapp 15 Sekunden. Kann man bestimmt noch ordentlich optimieren. :angel:
Ich weiß auf Anhieb nur nicht so recht, wie man die Anzahl der Möglichkeiten berechnen kann ... :gruebel:
Edit: Ok, bei 5 aus 26 sind das 26 * 25/2 * 24/3 * 23/4 * 22/5. Kann man sicherlich allgemein als Produkt schreiben, und hat bestimmt eine feste Bezeichnung in der Kombinatorik.
Edit2: Mit der Antwort von jfheins ist mir jetzt auch klar, wie diese Anzahl zustande kommt - :idea: - alle möglichen und dann die Permutationen wegdividieren, alles klar. :D
ub60 - Mi 29.01.20 23:01
Oh, das ist ja doch einfacher, als ich gedacht hatte. Genau das habe ich gesucht.
Danke dafür!
Zitat: |
... und hat bestimmt eine feste Bezeichnung in der Kombinatorik |
Ja, Binomialkoeffizient :) .
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!