Einzelnen Beitrag anzeigen

cherub

Registriert seit: 2. Aug 2010
2 Beiträge
 
Delphi 2 Desktop
 
#1

Suche schnellen kombinatorischen Algorithmus

  Alt 18. Feb 2011, 17:42
Hallo Leute, ich suche einen schnellen kombinatorischen Algorithmus zur Erzeugung von Kombinationen ohne Wiederholungen, d.h. keine Permutationen oder Variationen.

Hier ein Beispiel: Aus der Zahlenreihenfolge n = 1, 2, 3, 4
benötige ich die Kombinationen (sprich hier alle k von 4...1):

1234

123 124 134 234

12 13 14 23 24

1 2 3 4

Dazu muss ich sagen das ich schon einen Algorithmus bei Delphitreff gefunden habe (s.u.), der über Rekursion die Kombinationen erzeugt.
Leider bin ich bisher noch nicht soweit in den Programmierkünsten (sprich Anfänger) fortgeschritten, so das ich den Algorithmus nicht vollständig
verstehe. Denn ich möchte, wenn der Algorithmus eine Kombination erzeugt hat diese analysieren und wenn diese sagen wir mal dem Analysekriterium
entspricht, die procedure abbricht. Im Moment ist es, soweit ich verstehe das er alle Kombinationen von n über k in eine Stringliste schreibt. Bisher konnte ich feststellen das die Kombinationen so erzeugt werden, dass ich nicht während der Erzeugung "zwischenprüfen" kann.

Hier einmal die Procedure:

procedure EineStelle(n, k, Stelle, MinWert: Byte; Kombination: string; Ergebnis : TStrings);
var MaxWert, AktWert: Byte;
i : integer;
begin
for AktWert := MinWert to k - (n - Stelle) do begin
if (Stelle < n)
then EineStelle(n, k, Stelle+1, AktWert+1, Kombination + IntToStr(AktWert) + ' ')
else begin
Ergebnis.Add(Kombination + IntToStr(AktWert));
end;
end;
end;
end.

Ein weiteres Problem ist, das der Algorithmus schon bei einer z.B. 1...32 ziffrigen Reihenfolge Ewigkeiten benötigt um daraus Kombinationen zu erzeugen. Ich benötige aber mindestens 48 ziffrige Reihenfolgen. Bisher konnte ich in Erfahrung bringen das ein iterativer Algorithmus schneller sein könnte. Vielleicht könnte mir jemand Helfen, einen iterativen Algorithmus, da diese ja schneller sein sollen, zu finden. Eine unflexible Lösung über verschachtelte Schleifen, die für mich alle n über k erzeugen, würde mir im schlechtesten Fall auch reichen. Ich würde mich auch über andere Lösungswege freuen.
Danke schon mal im Voraus.

Geändert von cherub (18. Feb 2011 um 17:45 Uhr)
  Mit Zitat antworten Zitat