Suche schnellen kombinatorischen Algorithmus

[cherub]

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.

[rollstuhlfahrer]

Also einen wunderbar schnellen Algorithmus dafür wird es nicht geben, weil schon alleine das Ergebnis nicht in eine String-Liste passt. Mit 7,92e28 (4^48) Möglichkeiten ist das weit mehr, als in ein Array (32-Bit System) jemals reinpasst (2^31-1 Speicherplätze).

Was du vielleicht machen kannst, ist: Statt einer String-Liste ein Array verwenden, und diesem vorher die Länge zuweisen (du kannst sie ja berechnen). So muss das Array nicht bei jedem .Add() um ein Element vergrößert werden (Eine Liste ist intern ein Array).

Bernhard

PS: Das Ergebnis oben muss nicht unbedingt stimmen. Ich habe nur für deine 4 Elemente auf 48 Positionen verteilt die Anzahl der Möglichkeiten berechnet. Willst du auch noch deine 4 Elemente auf 47, 46, ..., 2, 1 Positionen verteilen musst du mit dem 5-fachen rechnen.

[jfheins]

Du hast dich um ein paar Zehnerpotenzen vertan. Denn er möchte ja nur die Kombinationen, nicht die Permutationen.

Bei 48 Ziffern gibt es also insgesamt 2,8 * 10^14 Ergebnisse. Das sprengt jedoch auch noch den Rahmen des Arbeitsspeichers. Wenn jedes Ergebnsi nur 1 Byte hätte, bräuchte man ca. 2^48 Byte, das sind 256 TB

Also entweder die Finger davon lassen, bis man 256 TB RAM Riegel kaufen kann oder einen Algorithmus benutzen, der das Zeug nicht speichert sondern jede Kombination nacheinander verarbeitet.

[rollstuhlfahrer]

Ich verstehe immer noch nicht ganz, warum man nur 2^48 Möglichkeiten hat (Das hilft mir auch nicht weiter: Wikipedia: Abzählende Kombinatorik), aber wenigstens darf ich mich in meiner Aussage bestätigt fühlen.

Bernhard

[jfheins]

Ich habe die Summe über alle n über k's gebildet.

Es gibt "48 über x" Möglichkeiten, x der 48 Elemente auszuwählen. Dann die Summer über alle x bilden.
Also:

Zitat:

sum(binomial(48, x), x, 1, 48) = 281474976710655

Sollte doch das sein, was der TE gewünscht hat, oder?

[cherub]

Danke bisher für die Antworten.
@ rollstuhlfahrer: Also die vier Elemente waren nur ein Bsp. dafür das ich alle Kombinationen aus den vier Elementen erzeugen möchte. Letztenendes möchte ich alle Kombinationen aus mind. 48 Elementen. Also wie jfheins sagte 48 über x.

Also wäre es, wie jfheins auch vorschlägt, am Besten ein Algo zu benutzen der nicht alle Kombinationen abspeichert und es möglich wäre sie alle nacheinander zu prüfen.

[David Martens]

Also wenn ich das richtig verstehe suchst du die erste Kombination die dein Kriterium erfüllt.

Na dann versuch es mal hiermit:

Delphi-Quellcode:

procedure EineStelle(n, k, Stelle, MinWert: Byte; Kombination, Ergebnis, Kriterium : string; gefunden : boolean);
var 
  MaxWert, AktWert: Byte;
  i : integer;
begin
  for AktWert := MinWert to k - (n - Stelle) do 
  begin
    if (Stelle < n) then 
    begin
      EineStelle(n, k, Stelle+1, AktWert+1, Kombination + IntToStr(AktWert) + ' ', Ergebnis, Kriterium, gefunden);
      if gefunden then
      begin
        Break;
      end;
    end
    else 
    begin
      if Kombination + IntToStr(AktWert) = Kriterium then
      begin
        Ergebnis := Kombination + IntToStr(AktWert);
        Break; // bricht die for schleife ab
      end;
    end;
  end;
end;