Interessante (?) Frage Kombinatorik

[Möbius]

Liebe Alle

Ich bin da auf ein Problem gestossen an dem ich mir die Zähne ausbeisse.
Angenommen ein Zahlenraum n.
n ist dann auch das grösste vorkommende Zeichen.
Die grösse der resultierenden Datei(en) sei n.

Also ist n=4 dann ist das Zielarray (x,x,x,x) gross.

Gesucht sind nun alle Zieldateien deren Quersumme n entspricht.
Also etwas
(4,0,0,0)
(0,4,0,0)
...
(3,1,0,0)
(3,0,1,0)
etc.

Also mit anderen Worten auch die Lösung für alle möglichen Dateien eine Summe n zu bilden mit Anzahl Summanden = n (einschliesslich der 0).

Kennt jemand hierfür einen Algorhitmus oder eine Lösung?
Wie liesse sich das effizient machen.

Vielen Dank und Grüsse
Reto

[blawen]

Etwa so etwas in dieser Art?
Sicher nicht perfekt, aber von der "Grundidee" her, sollte es passen.

Delphi-Quellcode:

procedure TForm7.Button1Click(Sender: TObject);
var
  n: Integer;
  current: array[0..3] of Integer;
begin
  n := 4; // Beispielwert

  Memo1.Clear;
  Memo1.Lines.Add('Alle Lösungen mit einer Quersumme von ' + IntToStr(n) + ':');
  FindeKombinationen(n, Length(current), 0, current);
end;

procedure TForm7.FindeKombinationen(n, k: Integer; idx: Integer; var current: array of Integer);
var
  i: Integer;
  Ausgabe: string;
begin
  if (idx = k) then
  begin
    // Wenn das Array vollständig ausgefüllt ist, prüfe die Summe
    if (current[0] + current[1] + current[2] + current[3] = n) then
    begin
      // Ausgabe in Memo
      Ausgabe := '(';
      for i := 0 to k - 1 do
      begin
        Ausgabe := Ausgabe + IntToStr(current[i]);
        if i < k - 1 then
          Ausgabe := Ausgabe + ', ';
      end;
      Ausgabe := Ausgabe + ')';
      Memo1.Lines.Add(Ausgabe);
    end;
    Exit;
  end;

  for i := 0 to n do
  begin
    current[idx] := i;
    FindeKombinationen(n, k, idx + 1, current);
  end;

[Möbius]

Lieber Roland

Ja genausowas in der Art.
So schlau war ich auch schon. Aber der Algorhitmus bildet alle Permutationen und prüft auf Quersumme 4.
Das ist leider sehr ineffizient.
Mich interessiert das ganze konkret für N = 256.
Und eben effizient...

Danke und GrRuss
Reto (Möbius)

[Olli73]

Hier ist eine Antwort, die ich mit Microsoft Copilot erhalten habe, der weltweit ersten KI-gestützten Antwort-Engine. Wählen Sie diese Option aus, um die vollständige Antwort anzuzeigen, oder probieren Sie sie selbst aus. https://sl.bing.net/AyhcbH3X52

[Olli73]

Oder allgemein:

Hier ist eine Antwort, die ich mit Microsoft Copilot erhalten habe, der weltweit ersten KI-gestützten Antwort-Engine. Wählen Sie diese Option aus, um die vollständige Antwort anzuzeigen, oder probieren Sie sie selbst aus. https://sl.bing.net/b9T8uMC15Ge

[blawen]

Verstehe ich es richtig, dass der Zahlenraum im gewünschten Fall 256^256 gross sein soll (n=256)?
Bei einem so grossen Bereich fehlt mir im Moment der Ansatz.

[Michael II]

Das ist ein typischer "Ziehen ohne Zurücklegen" Fall. n Kugeln, d Kugeln ziehen. n tief d Fälle.

Nimm zum Beispiel n=5 nummerierte Kugeln und ziehe aus diesen 2 Kugeln.

Alle Möglichkeiten aus 5 Kugeln 2 auszuwählen (insgesamt 5 tief 2 = 10 Fälle). Die gezogenen Kugeln markieren wir in der Liste mit X:

XX345
X2X45
X23X5
X234X
1XX45
1X3X5
1X34X
12XX5
12X4X
123XX

Die zwei X unterteilen jede gefundene Lösung in 3 Teile.
Wir können die Anzahl der Kugeln pro Teil zählen und in einen Vektor schreiben:

XX345 (0,0,3)
X2X45 (0,1,2)
X23X5 (0,2,1)
X234X (0,3,0)
1XX45 (1,0,2)
1X3X5 (1,1,1)
1X34X (1,2,0)
12XX5 (2,0,1)
12X4X (2,1,0)
123XX (3,0,0)

Die Ziehung 1X34X erzeugt den Vektor (1,2,0): Wir haben in dieser Ziehung die zwei Kugeln 2 und 5 gezogen (durch X markiert). Links von Kugel 2 liegt 1 Kugel (nämlich Kugel 1) [d.h. für unseren Vektor (1,.,.)], links von Kugel 5 liegen die 2 Kugeln 34 [d.h. (.,2,.)] und rechts von Kugel 5 liegt keine Kugel [(.,.,0)].


Wir haben mit diesem Beispiel den Fall "Wir wollen Vektoren mit 3 Elementen, die Summe der Vektorelemente soll 3 ergeben" gelöst.

Allgemein:

Du benötigst einen Vektor (x1,x2,x3,x4....xv) bestehend aus v Elementen.
Die Summe der v Vektorelemente xi soll s ergeben.

Wir wissen anhand des Beispiels oben: Wenn wir v-1 Kugeln ziehen, dann können wir wie oben beschrieben aus jeder Ziehung v Vektorelemente erzeugen.
Insgesamt sollten nach dem Ziehen der v-1 Kugeln noch s Kugeln im Topf liegen.

Wir müssen also den Fall "Aus n=v-1+s Kugeln ohne Zurücklegen d=v-1 Kugeln ziehen" berechnen.

Dies kannst du
- rekursiv lösen oder
- iterativ indem du alle möglichen Fälle durchnummerierst und aus jeder Nummer einen Vektor erzeugst.

[Olli73]

Aus welcher Aussage entnimmst du, dass es ohne zurücklegen ist?

[Michael II]

Lösung via Rekursion.
In s gibst du die gewünschte Summe an, in v die Anzahl der gewünschten Vektorelemente.

Wie erwähnt: Es geht auch iterativ, indem du von 1..n tief d zählst und aus jeder Nummer einen Vektor erzeugst.

Delphi-Quellcode:

procedure ZoZ(n, d: Integer; var A: array of Integer; i, m: Integer; var res : TStringList );
var
  j: Integer;
  hs, s : string;
begin
  A[i] := m;
  if i = d then
  begin
    s := '';
    for j := 1 to n-d do
      s := s + IntToStr(A[j]-A[j-1]-1) + ' ';
    res.Add(s);
  end
  else
  for j := m + 1 to n do ZoZ(n, d, A, i + 1, j,res);
end;

procedure TForm131.Button1Click(Sender: TObject);
var A : array of integer;
    s, v, n, d : integer;
    res : TStringList;
begin
   s := 4;  // Die Summe der Vektorelemente soll s ergeben.
   v := 4;  // Der Vektor soll v Elemente enthalten.

   d := v-1;
   n := s+d;

   setlength(A,d+2);
   A[0] := 0;
   A[d+1] := n+1;
   res := TStringList.Create;
   ZoZ( n, d, A, 0, 0, res );
   ShowMessage( res.Text );
   res.Free;
end;

[Michael II]

Zitat:

Zitat von Olli73 (Beitrag 1540196)

Aus welcher Aussage entnimmst du, dass es ohne zurücklegen ist?

Er will Vektoren von einer gewissen Länge v generieren und die Vektorelemente sollten aufsummiert s ergeben. Das löst man durch "Ziehen ohne Zurücklegen" - siehe mein Beispiel weiter oben.