Interessante (?) Frage Kombinatorik

[Uwe Raabe]

Ich hätte da einen iterativen Ansatz ohne Rekursion zu bieten:

Delphi-Quellcode:

procedure Kombinatorik(N: Integer; HandleArray: TProc<TArray<Integer>>);
var
  arr: TArray<Integer>;
begin
  SetLength(arr, N);
  { Triviale Startkombination }
  arr[0] := N;
  HandleArray(arr);
  var idx := 0;
  repeat
    if idx < High(arr) then begin
      { Schiebe einen Zähler um eine Stelle nach rechts }
      Dec(arr[idx]);
      Inc(idx);
      Inc(arr[idx]);
      HandleArray(arr);
    end
    else begin
      { Letzte Stelle: Merke und lösche den Übertrag }
      var K := arr[idx];
      arr[idx] := 0;
      { Suche den den größten Index mit einem Wert > 0. 
        Gibt es keinen sind wir fertig.}
      repeat
        Dec(idx);
        if idx < 0 then
          Exit;
      until arr[idx] > 0;
      { Setze den Übertrag in die nächste Stelle (muss 0 enthalten) }
      arr[idx + 1] := k;
      { Im weiteren Verlauf wird wieder ein Zähler von idx auf den Übertragswert geschoben }
    end;
  until False;
end;

Das Ergebnis sieht dann so aus:

Code:

4 0 0 0
3 1 0 0
3 0 1 0
3 0 0 1
2 2 0 0
2 1 1 0
2 1 0 1
2 0 2 0
2 0 1 1
2 0 0 2
1 3 0 0
1 2 1 0
1 2 0 1
1 1 2 0
1 1 1 1
1 1 0 2
1 0 3 0
1 0 2 1
1 0 1 2
1 0 0 3
0 4 0 0
0 3 1 0
0 3 0 1
0 2 2 0
0 2 1 1
0 2 0 2
0 1 3 0
0 1 2 1
0 1 1 2
0 1 0 3
0 0 4 0
0 0 3 1
0 0 2 2
0 0 1 3
0 0 0 4

[Michael II]

Ich bau solche Ziehungen auch fast nur iterativ auf, v.a. um Aufrufe zu verhindern.

Hier noch ein rekursiver direkter Ansatz (also ohne die "Ziehen ohne Zurücklegen" Überlegung).
[Damit man bei solchen Aufgaben das Rad nicht immer neu erfinden muss, lohnt es sich ein paar kombinatorische Aufgaben wie "Ziehen mit/ohne Zurücklegen", Permutationen etc. zu programmieren. Durch geschickte Parameterwahl kann man dank einer solchen Sammlung die meisten Probleme mit einer Zeile Code lösen.]

Delphi-Quellcode:

procedure af( rest : integer; var A: array of Integer; elnr : integer; var res : TStringList );
var i, j : integer;
    s : string;
begin
  if elnr = High(A) then // letzte Position in A erreicht
  begin
      s := '';
      A[elnr] := rest; // wir schreiben den Rest der Summe
      // und speichern A in res ab:
      for j := 0 to High(A) do s := s + A[j].ToString + ' ';
      res.Add(s);
  end else
  for i := 0 to rest do
  begin
    // an Postion elnr sind noch die Werte 0..rest möglich
    A[elnr] := i; 
    // danach können wir noch rest-i auf die Elemente A[elnr+1] .. A[High(A)] verteilen:
    af(rest-i, A, elnr+1, res);
  end;
end;

....
 res := TStringList.Create;
 Setlength(A,v);
 af(s,A,0,res);
 ShowMessage( res.Text );
 res.free;