Tugas

Tulis fungsi / program yang mengambil nparameter / input dan mencetak / mengembalikan jumlah topologi (yang diperlihatkan di bawah) pada set {1,2,...,n}.

Definisi Topologi

Misalkan X adalah himpunan terbatas apa pun, dan asumsikan bahwa T, yang merupakan himpunan bagian dari himpunan X (yaitu himpunan yang berisi himpunan bagian X), memenuhi persyaratan ini :

1. X dan set kosong di T.

2. Jika dua himpunan U dan V berada di T, maka penyatuan kedua himpunan tersebut berada di T.

3. Jika dua himpunan U dan V berada di T, maka perpotongan kedua himpunan tersebut berada di T.

... maka T disebut topologi pada X.

Spesifikasi

1. Program Anda adalah:

   • sebuah fungsi yang diambil nsebagai parameter
   • atau program yang menginput n

   dan mencetak atau mengembalikan jumlah topologi (berbeda) pada set {1,2,...,n}.

2. n adalah bilangan bulat non-negatif yang kurang dari 11 (tentu saja tidak ada masalah jika program Anda menangani n lebih besar dari 11), dan hasilnya adalah bilangan bulat positif.

3. Program Anda tidak boleh menggunakan segala jenis fungsi perpustakaan atau fungsi asli yang menghitung jumlah topologi secara langsung.

Input contoh (nilai n): 7

Contoh output / pengembalian: 9535241

Anda dapat memeriksa nilai pengembalian di sini atau di sini .

Tentu saja, kode terpendek menang.

Pemenangnya diputuskan, namun, saya dapat mengubah pemenang jika kode yang lebih pendek muncul ..

Haskell, 144 karakter

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]

Hampir implementasi langsung dari spesifikasi, modulo beberapa monad magic.

Sangat lambat untuk n > 4.

Python, 147 karakter

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

Cepat untuk N <= 6, lambat untuk N = 7, tidak mungkin N> = 8 akan pernah selesai.

Set individual diwakili oleh bitmask integer, dan topologi oleh set bitmask. S(i,K)menghitung jumlah topologi berbeda yang dapat Anda bentuk dengan memulai Kdan menambahkan set dengan bitmasks> = i.

Zsh, 83 karakter

Solusi ini cocok dengan surat persyaratan Anda (tetapi tidak, tentu saja, semangat). Tidak diragukan lagi ada cara untuk menekan angka lebih banyak lagi.

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

Python, 131 karakter

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

Versi yang diperluas:

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

Sebagai contoh, misalkan n = 3. Himpunan bagian yang mungkin dari [n] adalah

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

di mana bit ih menunjukkan apakah saya berada di subset. Untuk menyandikan himpunan bagian himpunan bagian, kami melihat bahwa masing-masing himpunan bagian ini milik atau tidak termasuk kelompok yang dimaksud. Jadi, misalnya,

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

menunjukkan bahwa x mengandung {}, {2}, dan {1,2,3}.