Teilermenge ermitteln

[alzaimar]

Zitat von Phistev:

Dann liefer doch mal eine iterative Lösung für folgendes Problem:

Du hast eine Menge mit n Elementen und möchtest alle Kombinationen mit 1,2,3,...,n-1 Elementen erhalten

Rekursiv geht relativ einfach, iterativ (fast) unmöglich, oder?

Nö:

Delphi-Quellcode:

Procedure Permutations (aString : String);
Var
  d : Array Of Integer;
  g, j, i, n, v : Integer;
  p,c : String;

Begin
  n := Length (aString);
  setlength (d,n+1);
  d[1] := 1;
  For i := 2 to n do
    d[i] := i * d[i-1];
  For i := 0 to d[n]-1 do begin
    c := aString;
    p := '';
    v := i;
    for j:=n-1 downto 1 do begin
      g := j - (v div d[j]) + 1;
      p := p + c[g];
      delete (c, g, 1);
      v := v mod d[j];
      End;
    p := p + c;
    memo1.lines.Add (p);
    End;
End;

Nachtrag:
Man kann den Algorithmus auch so umschreiben, das man direkt die N.te Permutation ausrechnet:

Delphi-Quellcode:

Function NthPermutation (aString : String; aCount : Integer) : String;
Var
  d : Array Of Integer;
  g, i, n : Integer;

Begin
  n := Length (aString);
  setlength (d, n);
  d[1] := 1;
  For i := 2 to n - 1 do d[i] := i * d[i-1];
  Result := '';
  for i := n-1 downto 1 do begin
    g := (aCount div d[i]) + 1;
    Result  := Result  + aString[g];
    delete (aString, g, 1);
    aCount := aCount mod d[i];
    End;
  Result := Result  + aString;
End;

Nicht sonderlich rekursiv, aber trotzdem schnell. Basiert im Übrigen auf der Inversen und Graycodes.