Berechnen Sie die Anzahl der Topologien für {1,2,…, n}

9

Aufgabe

Schreiben Sie eine Funktion / ein Programm, die / das nals Parameter / Eingabe verwendet und die Anzahl der Topologien (die unten gezeigt wird) auf dem Satz druckt / zurückgibt {1,2,...,n}.

Definition der Topologie

Sei X eine beliebige endliche Menge und nehme an, dass T, die Teilmenge der Potenzmenge von X ist (dh eine Menge, die Teilmengen von X enthält), diese Bedingungen erfüllt :

  1. X und die leere Menge sind in T.

  2. Wenn zwei Mengen U und V in T sind, dann ist die Vereinigung dieser beiden Mengen in T.

  3. Wenn zwei Mengen U und V in T sind, dann ist der Schnittpunkt dieser beiden Mengen in T.

... dann heißt T die Topologie auf X.

Spezifikationen

  1. Ihr Programm ist entweder:

    • eine Funktion, die nals Parameter verwendet wird
    • oder ein Programm, das eingibt n

    und druckt oder gibt die Anzahl der (unterschiedlichen) Topologien auf dem Satz zurück {1,2,...,n}.

  2. n ist eine nicht negative Ganzzahl, die kleiner als 11 ist (natürlich gibt es kein Problem, wenn Ihr Programm n größer als 11 verarbeitet), und die Ausgabe ist eine positive Ganzzahl.

  3. Ihr Programm sollte keine Bibliotheksfunktionen oder nativen Funktionen verwenden, die die Anzahl der Topologien direkt berechnen.

Beispieleingabe (Wert von n): 7

Beispiel für Ausgabe / Rückgabe: 9535241

Sie können Ihren Rückgabewert hier oder hier überprüfen .

Natürlich gewinnt der kürzeste Code.

Der Gewinner steht fest, ich kann den Gewinner jedoch ändern, wenn ein kürzerer Code angezeigt wird.

code-golf math set-theory JiminP
quelle
Muss es in diesem Jahrhundert Ergebnisse liefern, oder ist ein Korrektheitsnachweis gut genug?
Peter Taylor
@ Peter Tatsächlich habe ich keine Ahnung, wie lange es dauern wird. Daher ist der Nachweis der Richtigkeit des Programms gut genug, aber das Programm sollte dennoch in einer angemessenen Zeit ein Ergebnis liefern, wenn n klein ist, wie 4 ~ 5.
JiminP
@JiminP, es scheint, dass die Berechnung für n = 12 früher ein Papier wert war, und es gibt keine bekannte Formel. Für 4 oder 5 vermute ich, dass es in wenigen Minuten mit brutaler Gewalt machbar ist.
Peter Taylor
Ist die falsche Teilmenge von 2 ^ X auch eine Topologie?
FUZxxl
@FUZxxl: Ja. Ich denke, das nennt man die diskrete Topologie .
JiminP

Antworten:

4

Haskell, 144 Zeichen

import List
import Monad
p=filterM$const[True,False]
f n=sum[1|t<-p$p[1..n],let e=(`elem`t).sort,e[],e[1..n],all e$[union,intersect]`ap`t`ap`t]

Fast eine direkte Implementierung der Spezifikation, modulo etwas Monadenmagie.

Extrem langsam für n > 4.

Hammar
quelle
5

Python, 147 Zeichen

N=input()
S=lambda i,K:1+sum(0if len(set(j&k for k in K)-K)-1 else S(j+1,K|set(j|k for k in K))for j in range(i,2**N))
print S(1,set([0,2**N-1]))

Schnell für N <= 6, langsam für N = 7, unwahrscheinlich, dass N> = 8 jemals abgeschlossen wird.

Einzelne Sätze werden durch ganzzahlige Bitmasken und Topologien durch Sätze von Bitmasken dargestellt. S(i,K)Berechnet die Anzahl der unterschiedlichen Topologien, die Sie bilden können, Kindem Sie mit Bitmasken> = beginnen und Sätze hinzufügen i.

Keith Randall
quelle
0

Zsh, 83 Zeichen

Diese Lösung entspricht dem Buchstaben Ihrer Anforderungen (aber natürlich nicht dem Geist). Es gibt zweifellos eine Möglichkeit, die Zahlen noch weiter zu komprimieren.

a=(0 3 S 9U 5CT 4HO6 5ODFS AMOZQ1 T27JJPQ 36K023FKI HW0NJPW01R);echo $[1+36#$a[$1]]
Gilles 'SO - hör auf böse zu sein'
quelle