Tantangan
Mengingat satu set T
dari himpunan bagian dari himpunan berhingga S={1,2,3,...,n}
, menentukan apakah T
merupakan topologi atau tidak.
Penjelasan
The Powerset P(S)
dari beberapa set S
adalah himpunan semua himpunan bagian dari S
. Beberapa contoh:
S = {}, P(S) = {{}}
S = {1}, P(S) = {{}, {1}}
S = {1,2}, P(S) = {{}, {1}, {2}, {1,2}}
S = {1,2,3}, P(S) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Sebuah topologi T
di set S
adalah bagian dari P(S)
dengan sifat sebagai berikut:
{}
ada diT
danS
ada diT
- Jika
A
danB
berada di dalamT
maka persimpangan mereka jugaA ∩ B
- Jika
A
danB
berada di dalamT
begitu juga serikat merekaA ∪ B
*
* Definisi ini tidak sepenuhnya benar, tetapi itu benar untuk set yang terbatas, yang cukup untuk keperluan tantangan ini. Aksioma yang sebenarnya akan memungkinkan untuk serikat yang tak terbatas juga, tetapi itu tidak relevan dalam kasus yang terbatas.
Detail
- Anda dapat mengasumsikan bahwa
S = {1,2,...,n}
(atau sebagai alternatifS = {0,1,...,n}
) di manan
bilangan bulat terbesar yang muncul di setT
. - Format input fleksibel: Anda dapat menggunakan string, daftar daftar atau set daftar atau format serupa yang dapat ditangani oleh bahasa Anda. Anda juga dapat menggunakan set seperti
S = {0,1,...,n}
jika lebih nyaman. - Outputnya harus benar atau salah.
- Anda diizinkan untuk mengambil
n
(atau sebagai alternatifn+1
ataun-1
) sebagai input tambahan. - Jika Anda bekerja dengan daftar yang diurutkan, Anda dapat mengasumsikan bahwa angka-angka dalam suatu set diurutkan. Anda juga dapat mengasumsikan bahwa daftar tersebut memiliki urutan tertentu (misalnya leksikografis.
- Saat kami mewakili set, Anda dapat mengasumsikan bahwa tidak ada dua entri dari representasi-daftar yang sama.
Contohnya
Topologi
{{}} over {}
{{},{1}} over {1}
P(S) over S (see in the explanation)
{{},{1},{1,2}} over {1,2}
{{},{1},{2,3},{1,2,3}} over {1,2,3}
{{1}, {1,2,3}, {1,4,5,6}, {1,2,3,4,5,6}, {}, {2,3}, {4,5,6}, {2,3,4,5,6}}
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {1,2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}}
{{}, {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}, {1,2,3,4,5,6}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,7,8,9}}
{{}, {1}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}}
non-Topologi
{{1}} because {} is not contained
{{},{2}} because {1,2} is not contained
{{},{1,2},{2,3}} because the union {1,2,3} is not contained
{{},{1},{1,2},{2,3},{1,2,3}} because the intersection of {1,2} and {2,3} is not contained
{{},{1},{2},{3},{1,2},{2,3},{1,2,3}} because the union of {1} and {3} is not contained
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}} because {1,2,3,5} is missing
{{}, {1}, {2}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}} because {1,2} is missing
T
merupakan himpunan, saya pikir masuk akal untuk mengasumsikan bahwa tidak ada bagian dalam input yang diulang (yaitu{{}, {1,2}, {1,2}}
bukan input yang valid). Bisakah Anda menjelaskannya dalam tantangan, baik secara afirmatif atau negatif?Jawaban:
Python 2 ,
117999791 byteCobalah online!
Output melalui kode keluar
sumber
Haskell ,
95 89 7478 byteCobalah online!
Penjelasan:
sumber
[[],[2]]
? Ini topologi, tetapi tidak lebih dari yang tersirat ("Anda dapat menganggap bahwa ...") set.Mathematica,
87736663 byteDibawa
[T, n]
sebagai input.Penjelasan
Fungsi yang mengembalikan persimpangan dan penyatuan input
Peta yang berfungsi ke daftar input di level 1.
Ratakan hasilnya (
Outer
bagian mengembalikan sekelompok bersarangList
).Ambil persatuan antara daftar yang diratakan dan
{{}, S}
. Ini menghapus duplikat dan menambah{}
danS
ke daftar yang dihasilkan.Periksa apakah daftar dari atas sama dengan versi input yang diurutkan.
sumber
MATL , 38 byte
Input adalah matriks biner di mana setiap baris adalah set, setiap kolom adalah elemen, dan setiap entri menunjukkan keanggotaan. Misalnya,
{{},{1},{1,2}}
dinyatakan sebagai[0 0;1 0;1 1]
. Gunakan program Oktaf tertaut untuk mengkonversi ke format ini.Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
sumber
Python 2 ,
92 71122 byte&
dan|
singkatan untuk operasi yang ditetapkan.set()
asi-i
Lambda yang mengambil daftar set sebagai input, dan mengembalikan Benar / salah. Cukup periksa apakah ada set kosong dan persatuan dan persimpangan setiap set (dua set iterated sebagai
i
danj
) ada di daftar set yang diberikan.Cobalah online!
sumber
input()
keset()
dalam catatan kaki.set()
dengani-i
ataui^i
CJam (23 byte)
Test suite online . Ini adalah blok anonim (fungsi). Saya berasumsi
S = {0,1,...,n}
; blok mengambil array array yang diurutkan dann+1
sebagai parameter dan pergi0
atau1
di stack. Dalam hal{{}}
kode dan kerangka kerja pengujian mengasumsikan itun+1 = 0
.sumber
Pyth,
2423 byteSuite uji
Program ini mengambil input sebagai daftar daftar yang dipesan. Daftar dalam harus dalam urutan menaik dan daftar urutan harus diurutkan berdasarkan panjang kemudian secara leksikografis. Saya telah mengkonfirmasi bahwa ini adalah format input yang diperbolehkan. Angka mulai dari 0, dan N +1 juga diambil sebagai input.
Adapun cara kerjanya, kami menyaring apa pun yang tidak dalam P (S), lalu menambahkan S,,
[]
persimpangan setiap pasangan dan penyatuan setiap pasangan, deduplicate, dan memeriksa bahwa hasilnya sama dengan input.sumber
Aksioma, 358 byte
ungolfed dan hasil:
sumber