Interessante (?) Frage Kombinatorik

[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

[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]

Zitat von Olli73:

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.

[Olli73]

Er hätte schreiben sollen, ob z.B. (2, 2, 0, 0) zulässig ist oder nicht.

[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

[Möbius]

Vielen Dank Michael

Dein Coding funktioniert.
Er rechnet jetzt schon Stunden und gibt lauter richtige Resultate raus.

Im Prinzip interessiert mich vorerst mal eine Abschätzung der Lösung für n=255.
Aber eben da geht probieren über studieren. Mit Fakultät 256 kommt kein Rechner klar.

Jedenfals, Dein Ansatz funktioniert.
Lieder macht er aber sehr viele Iterationen bis es wieder zu einer Ausgabe kommt....

[shebang]

Zitat von Möbius:

Mit Fakultät 256 kommt kein Rechner klar.

Weil da eine Zahl mit über 500 Stellen herauskommt. Schau dir dazu am besten mal die Stirling Formel an.

[Michael II]

Zitat von Möbius:

Vielen Dank Michael

Dein Coding funktioniert.
Er rechnet jetzt schon Stunden und gibt lauter richtige Resultate raus.

Im Prinzip interessiert mich vorerst mal eine Abschätzung der Lösung für n=255.
Aber eben da geht probieren über studieren. Mit Fakultät 256 kommt kein Rechner klar.

Jedenfals, Dein Ansatz funktioniert.
Lieder macht er aber sehr viele Iterationen bis es wieder zu einer Ausgabe kommt....

Hallo Möbius,

Danke für dein Feedback. Punkto Anzahl Lösungen: Wie erwähnt, kann dein Problem auf "Ziehen ohne Zurücklegen (d Kugeln (oder was auch immer) aus insgesamt n ziehen ohne gezogene zurückzulegen)" zurückgeführt werden. Und da kennen wir die Anzahl Möglichkeiten (n tief d) = n!/(d!*(n-d)!), wobei für dein Problem d = v-1, und n = s+d, v = Länge des Vektors, s = gewünschte Summe. Wenn du die genaue Anzahl berechnen lassen willst, kannst du Mathematica, Maple o.ä. bemühen (Python kann's glaub auch - bin aber dort nicht zu Hause ). Oder Delphi mit BigInts...

Wenn du nur Näherungswerte benötigst, dann reicht sogar ein Taschenrechner der 1970er Jahre (oder natürlich Delphi). Du kannst ausnutzen, dass log(a*b)=log(a)+log(b) und damit g := Log(n!) = Log(1)+Log(2)+...+Log(n) ist. Am besten nimmst du den 10er Log. Wenn dein Resultat m,f lautet (m vor dem Komma, f nach dem Komma), dann lautet das Resultat für n! = 10^g ≈ (0,f)^10*10^m.

Punkto "Warten auf Ausgabe". Im Code, wo jeweils ein weiterer Vektor bekannt ist, könntest du direkt in ein File schreiben. Dann stopfst du bei "grossem n tief d" keine Riesen-TStringlist (bei grosser Lösungsmenge besser integer Array) in den Arbeitsspeicher.

Wie erwähnt "Rekursive Lösungen" sind oft besser zu lesen als iterative. Bei vielen verschachtelten rekursiven Aufrufen hast du bei einer iterativen Lösung (wie zum Beispiel Uwes) u.U. mehr Performance.