Berechnen Sie die effizienteste Binärfunktion

13

Heute werden wir die effizienteste Binärfunktion berechnen. Im Einzelnen berechnen wir die Funktion, die, wenn ein Ausdruck durch Anwenden der Funktion auf die konstante Eingabe 0 oder ihre eigene Ausgabe erstellt wird, alle positiven Ganzzahlen mit den kürzestmöglichen Ausdrücken darstellen kann, wobei den kleineren Ganzzahlen eine höhere Priorität eingeräumt wird.

Diese Funktion ist wie folgt aufgebaut:

Wählen Sie für jede Ganzzahl ab 1 den kürzesten Ausdruck, dem wir noch keine Ausgabe zugewiesen haben, und machen Sie diese Ganzzahl zur Ausgabe dieses Ausdrucks. Gleichheit in Ausdruckslänge wird durch kleineres linkes Argument und dann durch kleineres rechtes Argument getrennt. So funktioniert das:

  • Zu Beginn ist 1 nicht zugewiesen. Der kürzeste nicht zugewiesene Ausdruck ist f(0, 0), also setzen wir ihn auf 1.

  • Jetzt ist 2 nicht zugewiesen. Die kürzesten nicht zugewiesenen Ausdrücke sind f(f(0, 0), 0)= f(1, 0)und f(0, f(0, 0))= f(0, 1). Die Krawatten werden also in Richtung kleinerer linker Argumente gebrochen f(0, 1) = 2.

  • Der kürzeste nicht zugewiesene verbleibende Ausdruck ist f(f(0, 0), 0)= f(1, 0), also f(1, 0) = 3.

  • Jetzt haben wir keine Ausdrücke mehr mit nur 2 fs und 3 0s, also müssen wir von jedem einen weiteren hinzufügen. Das Brechen von Bindungen durch linkes Argument, dann rechtes Argument, bekommen wir f(0, 2) = 4da f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Weiter, haben wir f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Hier ist eine Tabelle, die ich für die ersten Werte ausgefüllt habe:

    0  1  2  3  4  5  6  7  8
 /---------------------------
0|  1  2  4  5  9 10 11 12 13
1|  3  6 14 15 37 38 39 40 41
2|  7 16 42 43
3|  8 17 44 45
4| 18 46
5| 19 47
6| 20 48
7| 21 49
8| 22 50

Eine andere Sichtweise ist, dass jeder Ausgang eine Größe hat, die der Summe der Größen seiner Eingänge plus eins entspricht. Die Tabelle wird in der Reihenfolge der Vergrößerung der Ausgabe ausgefüllt, wobei die Bindungen durch Minimierung der linken Eingabe und der rechten Eingabe aufgehoben werden.

Ihre Herausforderung besteht darin, bei zwei nicht negativen Ganzzahlen als Eingabe den Wert dieser Funktion zu berechnen und auszugeben. Das ist Code Golf. Die kürzeste Lösung in Bytes gewinnt. Standardlücken sind verboten.

isaacg
quelle
Sieht A072766 ähnlich , unterscheidet sich jedoch ab f (3, 1).
kennytm
2
Dies ist die erste Herausforderung seit einiger Zeit, die mich etwas verwirrt, effizient zu kalkulieren. Ich glaube, mit katalanischen Zahlen ist etwas möglich, aber ich kann nicht sofort an eine Lösung denken. Hmm ...
orlp
2
Okay, ich glaube nicht, dass dies eine gute Antwort auf Ihre Frage wäre. Um dies jedoch einigermaßen effizient zu gestalten, können Sie immer wieder katalanische Zahlen von den Funktionsargumenten abziehen, bis sie kleiner als die nächste katalanische Zahl sind. Dann haben Sie die Länge ihrer Ausdrücke gefunden. Dann können Sie die Ranking / unranking Funktionen von diesem Papier , mit der Modifikation, um das Ergebnis zu berechnen. Vielleicht ist es nach all dem möglich, Code-Teile in der Mitte "auszublenden" und eine einigermaßen elegante Lösung zu finden.
Orlp
Eigentlich funktioniert der Ansatz aus meinem vorherigen Kommentar nicht. ((0, (0, (0, 0))), 0)ist lexikographisch kleiner als (((0, 0), 0), (0, 0)), letztere hat jedoch eine kleinere linke Seite.
Orlp

Antworten:

6

Haskell, 110 Bytes

f q=head[i|let c=[(-1,0)]:[[(f a,f b)|n<-[0..k],a<-c!!n,b<-c!!(k-n)]|k<-[0..]],(p,i)<-zip(concat c)[0..],p==q]

Das Argument hier ist das Tupel (x,y). Ähnlich wie die Antwort oben, aber die Nachschlageliste enthält nur die linken und rechten Indexpaare anstelle der Bäume.

halfflat
quelle
1
Gute Antwort! head[...]ist [...]!!0und (p,i)<-zip(concat c)[0..]kann gekürzt werden (i,p)<-zip[0..]$id=<<c.
Laikoni
Danke für die Verbesserungen! Auf jeden Fall das Hinzufügen id=<<zum Repertoire :)
halfflat
5

Python 3, 154 Bytes

b=lambda n:[(l,r)for k in range(1,n)for l in b(k)for r in b(n-k)]+[0]*(n<2)
def f(x,y):r=sum((b(n)for n in range(1,x+y+3)),[]);return r.index((r[x],r[y]))

Es ist weder sehr schnell noch sehr golfen, aber es ist ein Anfang.

orlp
quelle
5

Beeindruckend! Ich habe es tatsächlich geschafft, einen effizienten Berechnungsalgorithmus zu erstellen. Das habe ich zunächst nicht erwartet. Die Lösung ist ziemlich elegant. Es leitet immer wieder mehr ab und kehrt dann bis zum Grundfall 0 zurück. In dieser Antwort bezeichnet die C (n) -Funktion die katalanischen Zahlen .

Der entscheidende erste Schritt ist das Bestätigen, dass es C (0) = 1 Werte der Länge Null gibt (nämlich 0 selbst), C (1) = 1 Werte der Länge Eins (nämlich f (0, 0)), C (2) = 2 Werte der Länge zwei (f (0, f (0, 0)) und f (f (0, 0), 0)).

Das heißt, wenn wir nach dem n-ten Ausdruck suchen und das größte k so finden, dass C (0) + C (1) + ... + C (k) <= n, dann wissen wir, dass n die Länge k hat .

Aber jetzt können wir weitermachen! Weil der gesuchte Ausdruck der n-C (0) -C (1) -C (k) -te Ausdruck in seiner Längenklasse ist.

Jetzt können wir einen ähnlichen Trick anwenden, um die Länge des linken Segments und dann den Rang innerhalb dieses Unterabschnitts zu ermitteln. Und dann greifen Sie auf die Reihen zurück, die wir gefunden haben!

Es wurde festgestellt, dass f (5030, 3749) = 1542317211 im Handumdrehen.

Python, nicht konkurrierend

def C(n):
    r = 1
    for i in range(n):
        r *= 2*n - i
        r //= i + 1
    return r//(n+1)

def unrank(n):
    if n == 0: return 0

    l = 0
    while C(l) <= n:
        n -= C(l)
        l += 1

    right_l = l - 1
    while right_l and n >= C(l - 1 - right_l) * C(right_l):
        n -= C(l - 1 - right_l) * C(right_l)
        right_l -= 1

    right_num = C(right_l)

    r_rank = n % right_num
    l_rank = n // right_num

    for sz in range(l - 1 - right_l): l_rank += C(sz)
    for sz in range(right_l): r_rank += C(sz)

    return (unrank(l_rank), unrank(r_rank))

def rank(e):
    if e == 0: return 0
    left, right = e

    l = str(e).count("(")
    left_l = str(left).count("(")
    right_l = str(right).count("(")
    right_num = C(right_l)

    n = sum(C(sz) for sz in range(l))
    n += sum(C(sz)*C(l - 1 - sz) for sz in range(left_l))

    n += (rank(left) - sum(C(sz) for sz in range(left_l))) * C(right_l)
    n += rank(right) - sum(C(sz) for sz in range(right_l))

    return n

def f(x, y):
    return rank((unrank(x), unrank(y)))

Ich bin mir ziemlich sicher, dass ich eine Menge unnötiger Berechnungen vornehme und viele Zwischenschritte entfernt werden könnten.

orlp
quelle