besondere Permutation, keine Anagramme!

[alzaimar]

Eins vorneweg: Wir wollen alle Variationen der Länge 0..N erstellen.

Ob man nun alle Möglichkeiten durchiteriert, oder das Problem rekursiv löst, kommt aufs Gleiche raus. Ich vermute aber, das der iterative Ansatz hier langsamer sein könnte, weil man jedesmal eine mögliche Lösung von Grund auf zusammenbaut. Das Prinzip mit der Bitmaske lässt sich aber so abwandeln, das die Zahlen anhand des Bitmusters summiert werden, und erst im Erfolgsfall die Lösung zusammengebastelt wird. Bei mehr als 64 Zahlen wird die Lösung aber sehr umständlich.

Dax irrt aber bei der Anzahl der Aufrufe, denn wir benötigen nicht N*N, sondern 2^N Aufrufe. (N=3, das sind 3 Bits und somit Zahlen 0..7, also 8 Stückerl)

Ich bevorzuge rekursive Lösungen, alleine deshalb, weil sie i.a. kompakt und eleganter sind (was immer das sein mag). Es ist aber letztendlich Geschmackssache. Auch finde ich sie einleuchtender, da sie den kombinatorischen Lösungsansatz direkt algorithmisch umsetzen.

Der Umweg über die Bitmaske ist wirklich trickreich, aber um die Ecke gedacht. Mit fehlender Eleganz hat das aber nicht zu tun, ganz im Gegenteil. Und wer vermutet schon Bitmasken in Verbindung mit der Erstellung aller Variationen.

Hier mein Senf:

Delphi-Quellcode:

  
Procedure FindeSumme(Const N : Array Of Integer; Const S : String; I0, T, X : Integer);
Var
  I : Integer;

Begin
  If T = X Then
    Form1.Memo.Lines.Add(S) // Lösung gefunden (Ausgabe häßlich, da Komma am Ende der Lösung...)
  Else
    For I := I0 To High(N) Do 
      If T + N[I]  <= GesuchteSumme Then
        FindeSumme(N, S + IntToStr(N[I]) + ', ', I + 1, T + N[I], X)
End;

...
  FindeSumme([1, 2, 3, 4, 10, 16, 21], '', 30);
...