Blasen anordnen

26

Hinweis: Herausforderung kopiert von der Frage, die bei math.stackexchange gestellt wurde .

Vor kurzem habe ich einige Fähigkeiten im Blasen von Blasen erlangt. Zuerst würde ich Blasen wie folgt blasen: Bildbeschreibung hier eingeben

Aber dann wurde es merkwürdig:

Bildbeschreibung hier eingeben

Nach einer Weile blies ich einige ziemlich seltsame Blasen:

Bildbeschreibung hier eingeben

Nachdem ich Hunderte, vielleicht sogar Tausende solcher Blasen geblasen hatte, runzelte meine Stirn plötzlich die Frage: Auf wie viele verschiedene Arten können Sie diese bei n Blasen anordnen? Wenn beispielsweise n = 1 ist, gibt es nur eine Anordnung. Wenn n = 2 ist, gibt es 2 Anordnungen. Wenn n = 3 ist, gibt es 4 Anordnungen. Wenn n = 4 ist, gibt es 9 Anordnungen.

Hier sind die 9 Arrangements von 4 Blasen:
Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Nachdem ich all diese wunderbaren Blasen gesprengt hatte, entschloss ich mich, die Freude, ihre Arrangements zu zählen, mit Ihnen zu teilen. Also hier ist deine Aufgabe:


Tor

Schreiben Sie ein Programm, eine Funktion oder Ähnliches, das die Anzahl der Arten zählt, wie Sie nBlasen anordnen können .


Eingang

n, die Anzahl der Blasen. n> 0


Ausgabe

Die Anzahl der Möglichkeiten, wie Sie diese Blasen anordnen können.


Gewinnkriterien

Es wäre wirklich cool, wenn wir eine Blase um Ihren Code werfen könnten. Je kleiner Sie Ihren Code machen, desto einfacher wird es sein, dies zu tun. Die Person, die den Code mit der geringsten Anzahl von Bytes erstellt, gewinnt den Wettbewerb.


Zusatzinformation

OEIS

Die Nummer eins
quelle
5
Wenn sich die Blasen schneiden können, ist dies ein offenes Problem mit 173 Lösungen für n = 4 .
Orlp
@orlp Zum Glück kreuzen sich diese Blasen nicht.
TheNumberOne
1
Ist 0eine gültige Eingabe?
Martin Ender
@ KenY-N Ja. Unten ist bereits ein OEIS-Link zu sehen
Roman Gräf,
Hoppla! Löschen Sie dumme Kommentar Zeit ...
Ken YN

Antworten:

12

Python 2, 92 87 Bytes

a=lambda n:n<2or sum((k%d<1)*d*a(d)*a(n-k)for k in range(1,n)for d in range(1,1+k))/~-n

Im Klartext: Zur Berechnung berechnen a(n)wir d*a(d)*a(n-k)für jeden Divisor djeder positiven ganzen Zahl, die kkleiner oder gleich ist n, addieren diese und dividieren durch n-1.

Um es schneller laufen zu lassen, führen Sie Python 3 aus (ersetzen Sie es /durch //in der obigen Funktion) und merken Sie sich:

import functools
a = functools.lru_cache(None)(a)

Wenn Sie dies tun, wird es a(50) = 425976989835141038353sofort berechnet .

orlp
quelle
Wow, das ist cool. Ich nehme an, dass sich lru_cache()die Funktion merkt?
Patrick Roberts
@PatrickRoberts Ja, normalerweise wird es als Funktionsdekorator verwendet, aber Sie können es auch manuell auf eine Funktion anwenden.
Orlp
@PatrickRoberts Hier sind die Dokumente fürlru_cache .
PM 2Ring
Diese Funktion gibt Truefür zurück n<2. Ich denke, das ist in Ordnung für n=1, da in Python Truein numerischen Kontexten 1 ausgewertet wird, aber a(0)0 zurückgegeben werden sollte. Sie könnten das mit beheben, n<2 and n or sum...aber es könnte einen kompakteren Weg geben.
PM 2Ring
Ich vermute, man kann argumentieren, dass es eine Möglichkeit gibt, null Blasen anzuordnen, aber das stimmt nicht mit A000081 überein. OTOH, wenn wir nur positiv lösen müssen, nkönnen wir diesen Eckfall ignorieren, da er die rekursiven Aufrufe für höhere Werte nicht beeinflusst n.
PM 2Ring
10

GNU Prolog, 98 Bytes

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.
c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Diese Antwort ist ein großartiges Beispiel dafür, wie Prolog selbst mit den einfachsten E / A-Formaten zu kämpfen hat. Es funktioniert im wahren Prolog-Stil, indem es das Problem beschreibt und nicht den Algorithmus, mit dem es gelöst werden soll: Es gibt an, was als legale Blasenanordnung gilt, und fordert Prolog auf, alle diese Blasenanordnungen zu generieren und sie dann zu zählen. Die Generierung dauert 55 Zeichen (die ersten beiden Zeilen des Programms). Das Zählen und E / A übernimmt die anderen 43 (die dritte Zeile und die neue Zeile, die die beiden Teile trennt). Ich wette, das ist kein Problem, das das OP Sprachen dazu bringen sollte, mit I / O zu kämpfen! (Hinweis: Die Syntaxhervorhebung von Stack Exchange macht das Lesen schwieriger und nicht einfacher. Deshalb habe ich sie deaktiviert.)

Erläuterung

Beginnen wir mit einer Pseudocode-Version eines ähnlichen Programms, das eigentlich nicht funktioniert:

b(Bubbles,Count) if map(b,Bubbles,BubbleCounts)
                and sum(BubbleCounts,InteriorCount)
                and Count is InteriorCount + 1
                and is_sorted(Bubbles).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Es sollte ziemlich klar sein, wie dies bfunktioniert: Wir repräsentieren Blasen über sortierte Listen (eine einfache Implementierung von Multisets, die bewirken, dass gleiche Multisets gleich sind), und eine einzelne Blase []hat eine Anzahl von 1, während eine größere Blase eine Anzahl hat Dies entspricht der Gesamtanzahl der Blasen in plus 1. Bei einer Anzahl von 4 würde dieses Programm (sofern es funktioniert) die folgenden Listen generieren:

[[],[],[],[]]
[[],[],[[]]]
[[],[[],[]]]
[[],[[[]]]]
[[[]],[[]]]
[[[],[],[]]]
[[[],[[]]]]
[[[[],[]]]]
[[[[[]]]]]

Dieses Programm ist aus mehreren Gründen als Antwort ungeeignet, aber das Dringlichste ist, dass Prolog eigentlich kein mapPrädikat hat (und das Schreiben würde zu viele Bytes erfordern ). Also schreiben wir das Programm stattdessen eher so:

b([], 0).
b([Head|Tail],Count) if b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and Count is HeadCount + TailCount + 1
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Das andere große Problem ist, dass es beim Ausführen in eine Endlosschleife gerät, da die Auswertungsreihenfolge von Prolog so funktioniert. Wir können die Endlosschleife jedoch lösen, indem wir das Programm leicht neu anordnen:

b([], 0).
b([Head|Tail],Count) if Count #= HeadCount + TailCount + 1
                    and b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

Dies könnte ziemlich seltsam aussehen - wir Addition der Zählungen , bevor wir wissen , was sie sind - aber GNU Prolog ist in #=der Lage, diese Art von nichtkausalen Arithmetik Handhabung und weil es die erste Zeile ist b, und das HeadCountund TailCountmüssen beide weniger als Count(was bekannt ist), dient es als Methode, um auf natürliche Weise zu begrenzen, wie oft der rekursive Term übereinstimmen kann, und bewirkt somit, dass das Programm immer beendet wird.

Der nächste Schritt ist das Golfspielen. Entfernen von Leerzeichen, Verwenden von Variablennamen mit einem Zeichen, Verwenden von Abkürzungen wie :-for ifund ,for and, Verwenden von setofanstatt listof(es hat einen kürzeren Namen und führt in diesem Fall zu den gleichen Ergebnissen) und Verwenden von sort0(X,X)anstatt is_sorted(X)(weil is_sortedes eigentlich keine echte Funktion ist) Ich habe es erfunden):

b([],0).
b([H|T],N):-N#=A+B+1,b(H,A),b(T,B),sort0([H|T],[H|T]).
c(X,Y):-setof(A,b(A,X),L),length(L,Y).

Das ist ziemlich kurz, aber es ist möglich, es besser zu machen. Die wichtigste Erkenntnis ist, dass die [H|T]Listensyntax sehr ausführlich ist. Wie Lisp-Programmierer wissen, besteht eine Liste im Grunde genommen nur aus Cons-Zellen, die im Grunde genommen nur Tupel sind, und kaum ein Teil dieses Programms verwendet List-Builtins. Prolog hat mehrere sehr kurze Tupelsyntaxen (mein Favorit ist A-B, aber mein zweiter Favorit ist A/B, den ich hier verwende, weil es in diesem Fall eine einfacher zu lesende Debug-Ausgabe erzeugt). und wir können auch unser eigenes einzelnes Zeichen nilfür das Ende der Liste wählen , anstatt an dem zwei Zeichen festzuhalten [](ich habe gewählt x, aber im Grunde funktioniert alles). Stattdessen [H|T]können wir also verwenden T/Hund die Ausgabe von erhaltenb das sieht so aus (beachte, dass die Sortierreihenfolge bei Tupeln ein wenig anders ist als bei Listen, daher sind diese nicht in der gleichen Reihenfolge wie oben):

x/x/x/x/x
x/x/x/(x/x)
x/(x/x)/(x/x)
x/x/(x/x/x)
x/(x/x/x/x)
x/x/(x/(x/x))
x/(x/x/(x/x))
x/(x/(x/x/x))
x/(x/(x/(x/x)))

Dies ist etwas schwerer zu lesen als die obigen verschachtelten Listen, aber es ist möglich. Überspringen Sie in Gedanken das xs und interpretieren Sie es /()als eine Blase (oder einfach /als eine entartete Blase ohne Inhalt, wenn es kein ()danach gibt), und die Elemente haben eine 1-zu-1-Entsprechung (wenn sie ungeordnet sind) mit der oben gezeigten Listenversion .

Natürlich hat diese Listendarstellung, obwohl sie viel kürzer ist, einen großen Nachteil; Es ist nicht in die Sprache integriert, daher können wir nicht sort0überprüfen, ob unsere Liste sortiert ist. sort0ist ohnehin ziemlich ausführlich, so dass es kein großer Verlust ist, es von Hand zu machen (in der Tat [H|T]kommt es auf genau die gleiche Anzahl von Bytes , wenn man es von Hand in der Listendarstellung macht). Die wichtigste Erkenntnis hier ist, dass das Programm in schriftlicher Form prüft, ob die Liste sortiert ist, ob ihr Ende sortiert ist, ob ihr Ende sortiert ist und so weiter. Es gibt viele redundante Überprüfungen, und das können wir ausnutzen. Stattdessen überprüfen wir nur, ob die ersten beiden Elemente in Ordnung sind (wodurch sichergestellt wird, dass die Liste sortiert wird, sobald die Liste selbst und alle ihre Suffixe überprüft wurden).

Das erste Element ist leicht zugänglich; Das ist nur der Kopf der Liste H. Das zweite Element ist jedoch schwieriger zu erreichen und existiert möglicherweise nicht. Zum Glück sind xes weniger als alle Tupel, die wir in Betracht ziehen (über den allgemeinen Vergleichsoperator von Prolog @>=), so dass wir das "zweite Element" einer Singleton-Liste für gut halten können xund das Programm gut funktionieren wird. Um auf das zweite Element tatsächlich zuzugreifen, besteht die schärfste Methode darin, ein drittes Argument (ein out-Argument) hinzuzufügen b, das xim Basisfall und Him rekursiven Fall zurückgegeben wird. Dies bedeutet, dass wir den Kopf des Endes als Ausgabe des zweiten rekursiven Aufrufs von erfassen können B, und natürlich ist der Kopf des Endes das zweite Element der Liste. So bsieht das jetzt aus:

b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.

Der Basisfall ist einfach genug (leere Liste, Rückgabe einer Anzahl von 0, das "erste Element" der leeren Liste ist x). Der rekursive Fall beginnt auf die gleiche Weise wie zuvor (nur mit der T/HNotation anstatt [H|T]und Hals extra-out-Argument); Wir ignorieren das zusätzliche Argument aus dem rekursiven Aufruf auf dem Kopf, speichern es aber Jin dem rekursiven Aufruf auf dem Schwanz. Dann müssen wir nur sicherstellen, dass die Liste Hgrößer oder gleich ist J(dh "wenn die Liste mindestens zwei Elemente enthält, ist das erste größer oder gleich dem zweiten), um sicherzustellen, dass die Liste sortiert endet.

Leider setofergibt sich ein Fit, wenn wir versuchen, die vorherige Definition von czusammen mit dieser neuen Definition von zu verwenden b, da unbenutzte Parameter mehr oder weniger wie bei SQL behandelt werden GROUP BY, was absolut nicht das ist, was wir wollen. Es ist möglich, es neu zu konfigurieren, um das zu tun, was wir wollen, aber diese Neukonfiguration kostet Zeichen. Stattdessen verwenden wir findall, was ein bequemeres Standardverhalten hat und nur zwei Zeichen länger ist, und geben uns diese Definition von c:

c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

Und das ist das komplette Programm; Erzeugen Sie kurzzeitig Blasenmuster und geben Sie dann eine ganze Menge Bytes zum Zählen aus (wir benötigen eine ziemlich lange Zeit findall, um den Generator in eine Liste umzuwandeln, dann eine unglücklicherweise ausführlich benannte length, um die Länge dieser Liste zu überprüfen, sowie das Boilerplate für eine Funktionsdeklaration).


quelle
"Prolog hat eigentlich kein Karten-Prädikat" : Prolog hat das maplist/2-8Prädikat , obwohl ich nicht sicher bin, ob dies die Dinge hier verkürzen wird.
Fatalize
@Fatalize: Huh, so wie es aussieht, wurde es in einer neueren Version hinzugefügt. Es ist nicht in der Dokumentation für die Installation, die ich habe, und es funktioniert in der Praxis nicht:| ?- maplist(reverse,[A,B]). uncaught exception: error(existence_error(procedure,maplist/2),top_level/0)
Das ist wirklich seltsam. maplistist ein sehr häufig verwendetes Prädikat, das in den wichtigsten Prolog-Distributionen (wie SWI-Prolog und SiCStus) enthalten ist
Fatalize
10

Mathematica, 68 Bytes

Ich wette, dies kann (sogar in Mathematica) mit einer von Grund auf neuen Implementierung besiegt werden, aber hier ist die integrierte Version:

<<NumericalDifferentialEquationAnalysis`
Last@ButcherTreeCount[#+1]&

ButcherTreeCountist 0-indiziert, daher das [#+1], und gibt eine Liste aller Werte bis zu seinem Argument zurück, daher das Last@. Ansonsten ist es nur das eingebaute Element für diese Funktion. Es muss jedoch ein Paket geladen werden, wie in der ersten Zeile beschrieben.

Greg Martin
quelle
8
"Natürlich hat Mathematica eine eingebaute Lösung dafür."
Orlp