Anzahl möglicher Relationen

19.06.2023, 06:40

Dopap

Anzahl möglicher Relationen

Ein elektrischer Kasten hat auf der Rückseite n Steckmuttern für elektrische Verbindungen. Diese dürfen und können bei Bedarf per einfachem Banansteckerkabel nur paarweise erfolgen.

Die Relationsvorschrift
Punkt x ist mit Punkt y verbunden ist injektiv und symmetrisch.
Es geht nun um die maximale Anzahl an möglichen SteckVerbingungen oder genauer um die Anzahl von möglichen Relationen.
Hier mal R(n) bezeichnet.

Man findet unschwer mit Blatt und Stift R(2)=2 , R(3)=4 R(4)=10.

Die Rekursion
$\begin{eqnarray*} R(n):=R(n-1)+(n-1)\cdot R(n-2) \quad \text{sowie}\quad R(1)=R(0)=1 \end{eqnarray*}$ , liefert
schrittweise und ebenfalls per Hand
R(5) = 26
R(6) = 76
R(7) = 232...

Beim rekursiven Aufruf von R(20) = 23 758 664 096 vergehen auf meinem TR ca. 35 min.

Praktisch wäre eine geschlossene algebraische Summen wie
R(n) = SUM(k=?,n,expression) die man am TR auch grafisch eingeben kann.
wie ist denn O(R(n)) einzuschätzen?

19.06.2023, 08:31

HAL 9000

Auf diesen Beitrag antworten »

RE: Anzahl möglicher Relationen

Zitat:

Original von Dopap
Beim rekursiven Aufruf von R(20) = 23 758 664 096 vergehen auf meinem TR ca. 35 min.

Das liegt aber nicht nur an der langsamen Hardware, sondern an ineffizienter Algorithmik: Wenn ich mal (in Python) die beiden Implementierungen

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

def R_slow(n):
    if n<=1:
        return 1
    return R_slow(n-1) + (n-1)*R_slow(n-2)

def R_fast(n):
    r0 = 1
    r1 = 1
    i = 1
    while i<n:
        r2 = r1
        r1 = r0
        r0 = r1 + i*r2
        i += 1
    return r0

vergleiche, dann dauert auf meiner Hardware der Aufruf von

R_slow(30) = 606917269909048576

etwa 0.372s, während

R_fast(2000) = 797013464918806470587706801475955832492925823695760651728040719418924648249
660879325311673532022852619233217802742159438265014071353609017561375245265
922609428374417630330324538279254459937701265377524859383803193430120320695
902780743611066677773927533168438816689057091703203956674103046384221984602
333564898408284041058352762566584336666966629513781147958146247441462236298
233829181214642919595683218667684462845992548415942019183971132438159070440
364822136378143677651199571260065386980619342798992646549122021042322696192
695795470590786222082082999057877816648365084405517104346776800600871354791
342146463249969598497636798728956840991028079247726487148054932474940184444
756387242289908123949514386816536985579623303765164362585160109410238160457
490384334084449752411368678950951605761197531238391141820982470447993082261
304087642965437800385133361787722690120482594031791248357355865150052597471
085379437234331523928826615918999674859840292303767477291281566241841907209
422346550082188559782972739225936242782553376676582001772726092130149911329
897989344549069234435459527148300989676522241394598380676337182125378258272
845531128195487451614074927022001440705887618154270791410943882842428356241
052077264198902489673832458772421434260479736333456779140083670673406065906
724206251545546105282620568509202428371490983117066806693254750075401569707
793703234839570116656880386763247076737760516491970579915660085648477255954
490815785432503991001113834282416569466765239351756871196223333279083039709
987451122728296499459738590267889872230458980437056755347913368543644433183
958112674329692295427079959557480631567165278949098006987463899033236832257
320570912406433761285482150280844208409040506191352018394359479706281419282
312589532526195977995426418291041797727663695950172139618537169107812864699
394736234889609048883363316319298002758278390199984474057526906419574695009
301623276550035201376202601933553630749317729764470078717743876612784743103
249861337920545075818097960589582700670149540810018346291914073103497184955
047143241652721167174486960988079188962126668322773645233852451721188244584
672130783427942345231356413534257993082924274976022970911052392216930242863
723149730883432021460951364807650612959047666257738949898903457384572284231
206250622748157334237370778609700023993000476902949893122724887875320282775
210534786114915428114971912367318139820009492336904789736669654064300323948
282002593304944778438571459948669799073175458423226955870818609730563081070
080686099386356080486709040537205438856004891134337235276077986242355681800
012414003203289205445885180133683316919337882095081512149197018290661556885
403783126655590034197044074271887264770292266573770229904268774515650906888
469970981893854452583240158619931659416879918312640579102354187644157714465
003462368130883650345621684683569116559010771465833353547754695257783511309
784146533405097878684044766662885376

nur etwa 0.00115s in Anspruch nimmt (die Zeit für die Zahlenausgabe auf dem Bildschirm wurde jeweils weggelassen). Dabei ist zu betonen, dass Python bei Integeroperationen tatsächlich exakt rechnet, bis zur letzten Stelle.

Jetzt noch ein wenig Mathematik: Die Abschätzung $\begin{eqnarray*} R(2n) = R(2n-1) + (2n-1)R(2n-2) \geq 2n R(2n-2) \end{eqnarray*}$ ergibt unmittelbar $\begin{eqnarray*} R(2n) \geq 2^n n! \end{eqnarray*}$ , was nach Stirling

$\begin{eqnarray*} \ln\left(R(2n)\right) > n\ln(2n) - n \end{eqnarray*}$ , sprich $\begin{eqnarray*} \ln\left(R(n)\right) > \frac{n}{2}\left[ \ln(n)-1\right] \end{eqnarray*}$

ergibt. Die o.g. Python-Berechnungen bis zu $\begin{eqnarray*} n=100000 \end{eqnarray*}$ lassen vermuten, dass an der Behauptung $\begin{eqnarray*} \lim_{n\to\infty} \frac{\ln\left(R(n)\right)}{n\ln(n)} = \frac{1}{2} \end{eqnarray*}$ was dran sein könnte.

20.06.2023, 11:08

Dopap

Auf diesen Beitrag antworten »

0.4s für R(30) trotz reiner Rekursion. Beeindruckender Maschineneinsatz!
Von R(2000) im Flash Gordon Stil ganz zu schweigen.

Ich dachte mathematisch mehr in Richtung und Hilfe von generierenden Funktionen um eine
deutliche Beschleunigung zu erreichen. Etwa so:

$\begin{eqnarray*} R(x)= \sum\limits_{n=o}^{\infty} \frac{R(n)}{n!} x^n \end{eqnarray*}$

ist evtl. möglich könnte aber relativ schwierig werden.

20.06.2023, 14:00

HAL 9000

Auf diesen Beitrag antworten »

Deine generierende Funktion ist an sich eine gute Idee: Mit $\begin{eqnarray*} f(x)= \sum_{n=0}^{\infty} \frac{R(n)}{n!} x^n \end{eqnarray*}$ kommt man rasch zu $\begin{eqnarray*} f(x) = e^{x+\frac{x^2}{2}} \end{eqnarray*}$ , was über das Cauchy-Produkt zur Koeffizientenformel

$\begin{eqnarray*} R(n) = n!\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor} \frac{1}{2^k(n-2k)!k!}\qquad (*) \end{eqnarray*}$

führt. Jetzt kann man sich trefflich streiten, was schneller geht: $\begin{eqnarray*} n \end{eqnarray*}$ -mal die definierende Iteration durchführen mit der durchdachten Variante (ergibt insgesamt genau $\begin{eqnarray*} n \end{eqnarray*}$ Multiplikationen), oder aber Formel (*) mit zwar nur ca. $\begin{eqnarray*} \frac{n}{2} \end{eqnarray*}$ Summanden, von denen jeder aber doch ein wenig aufwändigere Rechnung erfordert...

21.06.2023, 10:26

Dopap

Auf diesen Beitrag antworten »

genau mein Ding!
etwas umgeschrieben damit die Summanden stets integer bleiben:

$\begin{eqnarray*} R(2n) = \sum_{k=0}^{n} \frac{(2n)!}{2^k(2n-2k)!k!}\qquad \end{eqnarray*}$

Hauptsache es bleibt algebraisch und ungerades Argument ist mir nicht wichtig.

jetzt läuft R(20) im Höllentempo von 4.8 s.

21.06.2023, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
jetzt läuft R(20) im Höllentempo von 4.8 s.

Hast du denn überhaupt mal probiert, in welchem Tempo so etwas wie das obige R_fast auf deiner Maschine läuft? Wenn ich das richtig einschätze, dann bestimmt <1s, wenn nicht gar <0,1s . Augenzwinkern

Noch besser sieht man die Ganzzahligkeit in der Darstellung

$\begin{eqnarray*} R(2n) = \sum_{k=0}^n \binom{2n}{2k}\cdot (2k-1)!! \end{eqnarray*}$

unter Nutzung der Doppelfakultät.

Übrigens:

Wenn ich in der R_fast-Variante auf die Genauigkeit pfeife, d.h. mit Floating Point statt exakten Integerzahlen rechnet, dann bekomme ich mit Python das Ergebnis

$\begin{eqnarray*} R\left(10^8\right) \approx 3.895655 \cdot 10^{378\,289\,618} \end{eqnarray*}$

in 14.6s heraus - dabei erweist sich die Eigenschaft "Interpreter-Sprache" von Python bei diesem Algorithmus sicher als Bremse (das ist bei den sehr langen Integerzahlen weniger relevant, dort wird die meiste Zeit in den Bibliotheken der Langzahl-Arithmetik verbracht).

21.06.2023, 17:08

Dopap

Auf diesen Beitrag antworten »

Python ist eine Interpretersprache?

mein R_fast(20) in RPN Logik dauert jetzt 0.42 s.

Theoretisch könnte ich das kompilieren und der Hausbibliothek mit ihren ca. 860 teilweise
mächtigen Befehlen/Programmen hinzufügen, aber wozu auch?

21.06.2023, 17:11

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Python ist eine Interpretersprache?

Ja. Aber viele Bibliotheken sind dann doch kompiliert (in C++ o.ä. geschrieben), so dass sich oft kein wesentlicher Geschwindigkeitsnachteil ergibt. Bei sowas "handgemachten" wie hier allerdings schon.

Zum Vergleich: Als C++ kompiliert schmelzen die 14.6 s zu 0.13s zusammen, also auf weniger als 1/100. Es ist ja nun wirklich auch vom Aufwand her eine sehr primitive Iterationsschleife. Augenzwinkern

---------------------------------------------------------------------------------------------

Ich komme mal noch zurück auf die Größenordnung: Die eine Richtung hatte ich oben ja schon nachgewiesen, und es sieht ganz danach aus als gelte insgesamt

$\begin{eqnarray*} \frac{n}{2}\left(\ln(n)-1\right) < \ln\left(R(n)\right) \leq \frac{n}{2}\ln(n) \end{eqnarray*}$ gültig für alle $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ .

Nach genauerer Sichtung des Zahlenmaterials bis ca. $\begin{eqnarray*} n=10^8 \end{eqnarray*}$ wäre meine Vermutung, dass der Grenzwert

$\begin{eqnarray*} g = \lim_{n\to\infty} \left[ \ln\left(R(n)\right) - \frac{n}{2}\left(\ln(n)-1\right) - \sqrt{n}\right] \end{eqnarray*}$

existiert, mit $\begin{eqnarray*} g\approx -0.6 \end{eqnarray*}$ .

EDIT: Ach, hätte man schon viel eher mal nachschauen sollen: https://oeis.org/A000085

Das bestätigt meine Vermutung, und gibt sogar den genauen Wert an: $\begin{eqnarray*} g= -\frac{1+2\ln(2)}{4} \end{eqnarray*}$ . Damit ist auch

Zitat:

Original von Dopap
wie ist denn O(R(n)) einzuschätzen?

beantwortet: Es gilt

$\begin{eqnarray*} \lim_{n\to\infty} \frac{R(n)}{\left(\frac{n}{e}\right)^{\frac{n}{2}}\cdot e^{\sqrt{n}}} = \frac{1}{\sqrt{2\sqrt{e}}} \end{eqnarray*}$ .

EDIT (27.6.): Ok, an der Asympotik war Dopap (entgegen anders lautenden Aussagen im Eröffnungsposting) dann doch nicht mehr interessiert. Für ihn typisches Verhalten, kann ich nur sagen.

22.06.2023, 14:02

Finn_

Auf diesen Beitrag antworten »

Mit der Rekursion gibt es ja zwei Probleme:

(1) Die Komplexität ist zunächst exponentiell.
(2) Die maximale Rekursionstiefe, die die Laufzeitumgebung bietet, mag beschränkt sein.

Man kann die Rekursion nun in eine Iteration umwandeln, wie HAL das gemacht hat, wofür man die Rekursion allerdings als gedanklicher Zwischenschritt händisch in endrekursive Form transformieren muss, was kognitiven Aufwand macht bzw. wobei ein Fehler unterlaufen kann. Es ist in Python möglich, eine Funktionen höherer Ordnung zu implementieren, die die beiden Probleme mehr oder weniger automatisch löst.

Zur Auflösung von (1) ist eine Memoisierung dienlich. Darunter versteht man, dass bereits berechnete Werte in einem Cache abgelegt werden, auf den zurückgegriffen werden kann. Die ursprüngliche rekursiv definierte Funktion heiße f, der Cache heiße fc und sei ein Wörterbuch.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

import sys
sys.setrecursionlimit(10000)

def cache(fc):
    def cache_fc(f):
        def f_cached(n):
            if not n in fc: fc[n] = f(n)
            return fc[n]
        return f_cached
    return cache_fc

@cache({0: 1, 1: 1})
def R(n):
    return R(n-1) + (n-1)*R(n-2)

print(R(2000))

Problem (2) wurde hier mit setrecursionlimit umgangen, was man aber als bogus erachten kann. Nämlich ist der Aufrufstapel in CPython mit dem Aufrufstapel des Betriebssystems verwoben, welcher ebenfalls beschränkt ist. Unter Umständen müsste dieser also auch vergrößert werden, was man unter Linux mit ulimit -s GRÖSSE_IN_KB bewerkstelligen kann. Hier tritt allerdings vorher schon das weitere Problem des exorbitanten Speicherverbrauchs auf, da im Cache viele große Zahlen abgelegt werden.

Eine Alternative für Problem (2) bietet der kompliziertere Ansatz, einen eigenen Aufrufstapel zu implementieren. Um die aktuelle Berechnung beim rekursiven Aufruf unterbrechen zu können, wird die Funktion gegen eine Koroutine ersetzt. Die Unterbrechung vermittelt nun das Schlüsselwort yield. Zur iterativen Verarbeitung der Rekursion wird ein Trampolin-System konstruiert, das heißt, der Kontrollfluss soll zwischen der Hauptschleife und der nächsten Koroutine hin und her springen.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

def cache(fc):
    def trampoline(f):
        def f_iterative(n):
            stack = []
            g = f(n)
            y = None
            while True:
                try:
                    if y is None:
                        n = next(g)
                    else:
                        n = g.send(y)
                    if n in fc:
                        y = fc[n]
                    else:
                        g1 = f(n)
                        stack.append((g, n))
                        g = g1
                        y = None
                except StopIteration as result:
                    if len(stack) == 0:
                        return result.value
                    else:
                        (g, n) = stack.pop()
                        y = result.value
                        fc[n] = y
        return f_iterative
    return trampoline

@cache({0: 1, 1: 1})
def R(n):
    return (yield n-1) + (n-1)*(yield n-2)

print(R(2000))

22.06.2023, 15:46

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
was kognitiven Aufwand macht bzw. wobei ein Fehler unterlaufen kann.

Bei diesem Typ Rekursion wie hier wohl kaum, d.h. wo auf eine definierte Anzahl direkter Vorgänger zugegriffen wird. Und für die wirkt der von dir betriebene Aufwand auch wie der reinste Overkill (wie angemerkt besteht Dopaps Iteration lediglich aus einer Addition und einer Multiplikation). Außerdem wird für $\begin{eqnarray*} n=10^8 \end{eqnarray*}$ der Cache schon ganz schön groß, aber Ok: In Zeiten wo RAM-Ausbau 32GB schon Standard ist, mag das verkraftbar sein.

Anders sieht es sicher aus für Rekursionen, die auf "wildere" Vorgänger zugreifen, z.B. $\begin{eqnarray*} R(n) = R\left(\left\lfloor \frac{n}{2}\right\rfloor\right) + n\cdot R\left(\left\lfloor \sqrt{n} \right\rfloor\right) \end{eqnarray*}$ , oder beispielsweise auch Rekursion in mehr als einer Dimension, da haben die von dir vorgeschlagenen Maßnahmen sicher einen positiven Effekt. Ich kenne sowas vom CAS MuPAD, wo man rekursiv definierte Funktion mit der Option "remember" versehen kann, und dort wirkt auch so ein Ergebniscache.

22.06.2023, 18:16

Finn_

Auf diesen Beitrag antworten »

Ein weniger flexibles, dafür aber unkompliziertes Utensil böte noch dieser simple Löser für herkömmliche Differenzengleichungen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

def solve(n0, y0, cb):
    def f(n):
        y = y0; order = len(y0)
        for k in range(n0 + order, n + 1):
            y.append(cb(y, k))
            y[k - order] = None
        return y[n]
    return f

R = solve(0, [1, 1], lambda R, n: R[n-1] + (n-1)*R[n-2])
print(R(2000))

28.06.2023, 09:29

Dopap

Auf diesen Beitrag antworten »

breiter Dialog und (über) reichlich Hinweise und Lösungen!
Sorry, hatte wohl das anscheinend unabdingbare Dankeschön als Abschluss vergessen.
Man wird eben auch nicht jünger.

28.06.2023, 10:12

HAL 9000

Auf diesen Beitrag antworten »

Ich finde das asymptotische Verhalten (beweismäßig nicht auf meinem Mist gewachsen, wie oben erwähnt)

$\begin{eqnarray*} R(n) \approx \frac{1}{\sqrt{2\sqrt{e}}}\cdot \left(\frac{n}{e}\right)^{\frac{n}{2}}\cdot e^{\sqrt{n}} \end{eqnarray*}$

schon bemerkenswert: Einerseits erinnert es vom Hauptwachstumsfaktor $\begin{eqnarray*} \left(\frac{n}{e}\right)^{\frac{n}{2}} \end{eqnarray*}$ her an Stirling $\begin{eqnarray*} n!\approx \sqrt{2\pi n}\cdot \left(\frac{n}{e}\right)^n \end{eqnarray*}$ - was mit dem über dem Daumen gepeilten $\begin{eqnarray*} R(n)\approx n\cdot R(n-2) \end{eqnarray*}$ und damit $\begin{eqnarray*} R(n)\approx \sqrt{n}\cdot R(n-1) \end{eqnarray*}$ irgendwie plausibel scheint - andererseits ist da dieser (vergleichsweise) kleine Schlenker $\begin{eqnarray*} e^{\sqrt{n}} \end{eqnarray*}$ noch drin.

Neue Frage »

Antworten »

Anzahl möglicher Relationen

Verwandte Themen