Autor Beitrag
ub60
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 722
Erhaltene Danke: 119



BeitragVerfasst: Mi 29.01.20 21:22 
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:

ausblenden 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

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8473
Erhaltene Danke: 447

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 29.01.20 22:40 
Das fand ich jetzt ne nette kleine Übung. Mein Ansatz:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
// Target: Die Stringliste, in die die Liste mit Wörtern rein soll.
// Source: Der String, aus dem die Wörter zusammengesetzt sein sollen, z.B. "ABCDEFG"
// IndexS: Der aktuelle Index in Source, über den iteriert werden soll
// lMax: die Länge der gesuchten Wörter, z.B. 3
// currentEntry: Das bisher im aktuellen Ast der Rekursion aufgebaute Wort, initial Leerstring
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
        // Zeichen anhängen
        newEntry := currentEntry + Source[i];
        // wenn die gewünschte Länge erreicht ist: Ausgabe
        if Length(newEntry) = lMax then
            Target.Add(newEntry)
        // sonst: rekursiv an der nächsten Stelle weitermachen
        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.

ausblenden 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

_________________
We are, we were and will not be.


Zuletzt bearbeitet von Gausi am Mi 29.01.20 23:03, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: ub60
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 886
Erhaltene Danke: 149

Win7
VS 2013, VS2015
BeitragVerfasst: Mi 29.01.20 22:58 
Du suchst Kombinationen ohne Wiederholung

Dazu müsste es sogar in Delphi unzählige Implementierungen geben ;-)


Zuletzt bearbeitet von jfheins am Sa 01.02.20 17:48, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: ub60
ub60 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 722
Erhaltene Danke: 119



BeitragVerfasst: Do 30.01.20 00: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 :) .