Zadanie

Napisz funkcję / program, który przyjmuje njako parametr / dane wejściowe i wypisuje / zwraca liczbę topologii (co pokazano poniżej) na zestawie {1,2,...,n}.

Definicja topologii

Niech X będzie dowolnym zbiorem skończonym i załóżmy, że T, który jest podzbiorem zbioru mocy X (tj. Zbioru zawierającego podzbiory X), spełnia następujące warunki :

1. X i pusty zestaw znajdują się w T.

2. Jeśli dwa zbiory U i V są w T, to połączenie tych dwóch zbiorów jest w T.

3. Jeśli dwa zbiory U i V znajdują się w T, to przecięcie tych dwóch zbiorów znajduje się w T.

... wtedy T nazywa się topologią X.

Dane techniczne

1. Twój program to:

   • funkcja, która przyjmuje njako parametr
   • lub program, który wprowadza n

   i drukuje lub zwraca liczbę (odrębnych) topologii w zestawie {1,2,...,n}.

2. n jest dowolną nieujemną liczbą całkowitą, która jest mniejsza niż 11 (oczywiście nie ma problemu, jeśli twój program obsługuje n większą niż 11), a wynik jest liczbą całkowitą dodatnią.

3. Twój program nie powinien używać żadnych funkcji bibliotecznych ani funkcji rodzimych, które bezpośrednio obliczają liczbę topologii.

Przykładowe dane wejściowe (wartość n): 7

Przykładowe wyjście / powrót: 9535241

Możesz sprawdzić wartość zwrotu tutaj lub tutaj .

Oczywiście, najkrótszy kod wygrywa.

Zwycięzca zostaje wyłoniony, jednak mogę go zmienić, jeśli pojawi się krótszy kod.

Haskell, 144 znaków

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]

Prawie bezpośrednia implementacja specyfikacji, modulo trochę magii monad.

Niezwykle wolno dla n > 4.

Python, 147 znaków

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]))

Szybkie dla N <= 6, wolne dla N = 7, mało prawdopodobne, aby N> = 8 kiedykolwiek się zakończyło.

Poszczególne zestawy są reprezentowane przez całkowite maski bitowe, a topologie przez zestawy bitmask. S(i,K)oblicza liczbę różnych topologii, które można utworzyć, zaczynając od Ki dodając zestawy z maskami bitowymi> = i.

Zsh, 83 znaki

To rozwiązanie odpowiada literze twoich wymagań (ale nie ducha, oczywiście). Niewątpliwie istnieje sposób na jeszcze większe skompresowanie liczb.

a=(0 3 S 9U 5CT 4HO6 5ODFS AMOZQ1 T27JJPQ 36K023FKI HW0NJPW01R);echo $[1+36#$a[$1]]

Python, 131 znaków

lambda n:sum(x&(x>>2**n-1)&all((~(x>>i&x>>j)|x>>(i|j)&x>>(i&j))&1 for i in range(2**n)for j in range(2**n))for x in range(2**2**n))

Wersja rozszerzona:

def f(n):
    count = 0
    for x in range(2**2**n): # for every set x of subsets of [n] = {1,...,n}
        try:
            assert x & 1 # {} is in x
            assert (x >> 2 ** n - 1) & 1 # [n] is in x
            for i in range(2**n): # for every subset i of [n]...
                if x >> i & 1: # ...in x
                    for j in range(2**n): # for every subset j of [n]...
                        if x >> j & 1: # ...in x
                            assert (x >> (i | j)) & 1 # their union is in x
                            assert (x >> (i & j)) & 1 # their intersection is in x
            count += 1
        except AssertionError:
            pass
    return count

Załóżmy na przykład, że n = 3. Możliwe podzbiory [n] to

0b000
0b001
0b010
0b011
0b100
0b101
0b110
0b111

gdzie i-ty bit wskazuje, czy i znajduje się w podzbiorze. Do kodowania zestawy podzbiorów, zauważamy, że każdy z tych podzbiorów albo należy, albo nie należy do danego zestawu. Tak więc na przykład

x = 0b10100001
0b000 # 1
0b001 # 0
0b010 # 1
0b011 # 0
0b100 # 0
0b101 # 0
0b110 # 0
0b111 # 1

wskazuje, że x zawiera {}, {2} i {1,2,3}.