Interessante (?) Frage Kombinatorik

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

[Uwe Raabe]

Bei N = 4 erzeugt mein Algorithmus 35 Ausgaben, bei N = 10 sind es schon 92378, bei N = 16 sind es 300540195. Die Zahl entspricht dem Binomialkoeffizient (n über k) mit n = 2*N-1 und k = N-1. Jedes N + 1 erzeugt knapp 4x so viele Ausgaben wie N. Damit kannst du in etwa abschätzen, wie lange es bei N = 256 wohl dauern wird. (Hinweis: Die Zahl ist ca. 4,7e+152. Dauert eine Iteration lediglich eine Nanosekunde, dann sind das ca. 4,7e+143 Sekunden oder ca. 1,5e+136 Jahre. Zum Vergleich: Das Universum ist heute ca. 1,4e+10 Jahre alt.)

Auch eine Parallelisierung würde nur wenig bringen, denn wenn ich das ohne Overhead auf 4 Kerne verteilen könnte, würde das immer noch solange dauern, als würde ich statt N = 256 nur N = 255 vorgeben. Bei 16 Cores wäre es dann so schnell wie N = 254.

[Sinspin]

Das waren noch Zeiten als solche Probleme hier oder in der EE im Zwei-Wochen-Takt besprochen wurden. Leider sind die meißten Experten von damals bereits in ihrer nächsten Inkarnation und aktuell zu jung um helfen zu können.
Keine Ahnung ob Fiete (Wolfgang) aus der EE Lust hätte etwas dazu zu sagen.
Ich hätte Lust, leider nur wenig Zeit.
Das wäre auf jeden Fall etwas was man mit Multithreading leicht beschleunigen könnte. Bin gerade am überlegen was eine GraKa von der Arbeit halten würde.

[Michael II]

Zitat von Sinspin:

Bin gerade am überlegen was eine GraKa von der Arbeit halten würde.

Eine Grafikkarte hat an (wie vorliegend) O(4^n) Problemen keine Freude. Spannend für GPU Berechnungen sind Algorithmen mit linearer, linear logarithmischer, allenfalls polynomialer Komplexität.

Im 1000Euro Bereich hat eine NVIDIA RTX3080 10'240 CUDA Kerne; Wenn du alle rechnen lässt, dann kannst du von Uwes weiter oben berechneten 10^136 Jahren 5 vom Exponenten nehmen .

Nebenbei: In #18 sollte stehen: n! = 10^g ≈ 10^(0,f)*10^m, Beispiel 4! = 10^log(4!) = 10^log(1*2*3*4) = 10^(log(1)+log(2)+log(3)+log(4)). Die Summe s der logs kannst du auch für sehr grosse n noch mit einem Taschenrechner berechnen. Hier s=1.38021... - 10^1.38021... = 10^0.38021*10^1 = 2.4*10^1.
Ohne log rechnen: Bei n tief d = n!/(d!*(n-d)!) rechnest du die drei Fakultäten nicht einzeln, du kannst den Bruch kürzen und vermeidest so u.U. Overflows, wenn du mit grossen Werten rechnest. Beispiel 1024 tief 2 = 1024!/(2!*1022!) = 1024*1023/2