Diberikan beberapa set, misalnya s1={2,3,7}, s2={1,2,4,7,8}dan s3={4,7}, diagram Venn memvisualisasikan setiap set dengan kurva tertutup dan elemen set yang baik di dalam atau di luar perimeter kurva, tergantung pada apakah mereka merupakan elemen set atau tidak. Karena semua elemen himpunan hanya muncul satu kali dalam digram Venn, kurva yang mewakili setiap himpunan perlu tumpang tindih jika elemen ada di lebih dari satu himpunan. Kami menyebut masing-masing sel yang tumpang tindih tersebut sebagai diagram Venn.

Penjelasan ini mungkin agak membingungkan, jadi mari kita lihat sebuah contoh.

Contoh

Diagram Venn untuk set s1, s2dan s3bisa terlihat seperti ini:

Sel-sel dari diagram Venn ini (dibaca dari atas ke bawah, kiri ke kanan) {1,8}, {2}, {7}, {4}, {3}, {}dan {}.

Dalam praktiknya, seseorang biasanya hanya menemukan diagram Venn dari dua atau tiga set, karena representasi diagram Venn dari empat set atau lebih tidak terlalu jelas. Namun mereka ada, misalnya untuk enam set:

^{CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1472309}

Tugas

Diberikan satu set himpunan bilangan bulat positif dalam representasi yang masuk akal, kembalikan set sel dari diagram Venn set input. Secara khusus, tidak diperlukan representasi grafis.

• Anda dapat menulis program atau fungsi lengkap.
• Anda dapat mengembalikan set kosong sebanyak ada sel kosong (yaitu daftar semua sel) alih-alih hanya satu set kosong (yaitu set sel).
• Beberapa cara yang wajar masukan untuk contoh di atas termasuk tetapi tidak terbatas pada {{2,3,7},{1,2,4,7,8},{4,7}}, [[2,3,7],[1,2,4,7,8],[4,7]], "2,3,7;1,2,4,7,8;4,7"atau "2 3 7\n1 2 4 7 8\n4 7". Jika ragu apakah format input yang Anda pilih dapat diterima, jangan ragu untuk bertanya dalam komentar.
• Format output Anda harus sesuai dengan format input Anda, jika memungkinkan. Perhatikan bahwa aturan ini mengharuskan format Anda untuk dapat menampilkan set kosong yang jelas.
• Ini kode-golf , jadi coba gunakan sesedikit mungkin byte dalam bahasa pilihan Anda. Untuk mendorong persaingan per bahasa alih-alih antar bahasa, saya tidak akan menerima jawaban.

Uji Kasus

Berikut adalah beberapa input bersama dengan kemungkinan output:

input -> output
{{2,3,7},{1,2,4,7,8},{4,7}} -> {{1,8},{2},{7},{4},{3},{}} (or {{1,8},{2},{7},{4},{3},{},{}})
{{1,2,3},{4,5,6},{7,8,9}} -> {{1,2,3},{4,5,6},{7,8,9},{}}
{{}} -> {{}}
{{1,2,3},{1,2}} -> {{1,2},{3},{}}
{{4,3,8},{1,2,9,3},{14,7,8,5},{6,11,3,8},{10},{9,4,3,7,10}} -> {{6,11},{10},{4},{3},{8},{5,14},{1,2},{9},{7},{}}
{{2,3,4,7},{},{1,3,7,5,6},{2,3,7,5},{7,2,4,3,6},{1,4,5}} -> {{},{4},{2},{7,3},{1},{6},{5}}
{{1,2,3,4},{1,2,5,6},{1,3,5,7}} -> {{4},{3},{2},{1},{6},{5},{7}}

Haskell , 71 byte

Fungsi anonim mengambil daftar daftar bilangan bulat dan mengembalikan daftar serupa.

Gunakan sebagai (foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[])[[1,2,3],[1,2]].

import Data.List
foldr(\x r->(x\\(id=<<r)):([intersect x,(\\x)]<*>r))[]

Cobalah online!

Bagaimana itu bekerja

• Menggunakan operasi set-like \\(perbedaan) dan intersectdari Data.List.
• Lipat daftar "set" (diwakili sebagai daftar) ke dalam daftar sel, dimulai dengan daftar kosong [].
• xadalah set saat ini yang akan ditambahkan ke diagram, dan rmerupakan daftar sel yang sudah dibangun.
  • x\\(id=<<r)adalah himpunan bagian dari elemen xyang tidak ada dalam sel yang sudah dibangun.
  • [intersect x,(\\x)]<*>rmembagi masing-masing sel rsesuai dengan apakah unsur-unsurnya ada xatau tidak.
• Paling pasti tidak berusaha untuk menggabungkan sel-sel kosong, jadi ada cukup banyak dari mereka di output.

Jelly , 14 17 byte

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€

Cobalah online!

Pengiriman fungsi (karena format Jelly mencetak daftar secara default tidak bolak-balik - ia tidak dapat membaca format outputnya sendiri - tetapi suatu fungsi input dan output dalam format yang sama). TIO link berisi footer yang menjalankan fungsi dan mencetak hasilnya dalam format yang sama dengan input yang diuraikan.

Penjelasan

FṀ‘³iþ¬Ḅµ;ṀḶ$ĠṖṖ€
FṀ‘               Find the largest number that appears in any of the input sets, + 1
   ³ þ            For each number from 1 to that number, and each of the input sets
    i ¬             find whether the number is missing from the set
       Ḅ          Convert the list of missing sets into a single number using binary
         ;        Append
        µ ṀḶ$     all numbers from 0 to the maximum value minus 1
             Ġ    Group indexes by values
              ṖṖ€ Delete the last group and last element of other groups

Persyaratan yang kami hasilkan setidaknya satu set kosong jika tidak semua bagian diagram Venn berhasil mengelola lebih dari setengah program di sini (ini bertanggung jawab untuk ’memastikan kami memiliki setidaknya satu grup untuk elemen yang tidak cocok, yang memungkinkan kami untuk melacak berapa set awalnya ada, ditambah sembilan byte terakhir dari kode sumber kecuali untuk Ġ). Cara dasar di mana kita menerapkannya adalah untuk memastikan bahwa semua 2 ^ n diagram Venn himpunan bagian memiliki setidaknya satu entri, dengan menambahkan entri dummy yang akan mengisi "tidak set" bagian dan (kemudian) entri dummy untuk setiap bagian lain, maka Ġakan menampilkan grup untuk setiap subset, yang dapat kita hapus menggunakan ṖṖ€.

Perl 5, 79 byte

sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h}

Mengambil input sebagai daftar array anonim seperti ([2,3,7], [1,2,4,7,8], [4,7]). Output hash di mana kunci adalah label dan nilainya adalah array anonim yang sesuai dengan set output.

Sebagai bagian dari program lengkap:

*x=
sub{for$.(0..@_){$x{$_}+=2**$.for@{$_[$.]}};push@{$h{$x{$_}}},$_ for keys%x;%h};
%x=x([2,3,7],[1,2,4,7,8],[4,7]);
print"Set $_:@{$x{$_}}\n"for keys%x;

Penjelasan:

Memberikan masing-masing set integer sebagai label $.,. Membuat hash yang menyimpan integer untuk setiap elemen unik $_. Menambahkan 2**$.untuk setiap set yang $_muncul, secara efektif membuat peta biner yang menunjukkan set mana setiap elemen muncul. Akhirnya, buat array anonim untuk setiap sel diagram Venn dan tekan elemen yang muncul dalam set yang sesuai ke array. Jadi setiap elemen dari setiap array ada dalam set yang sama dan dengan demikian sel yang sama dari diagram Venn.

Pyth , 11 byte

m-@Fds-Qdty

Suite uji.

Bagaimana itu bekerja

Setiap wilayah diagram Venn mewakili elemen yang ada di [kombinasi tertentu dari set] tetapi tidak di [set lainnya].

Jadi, kami menghasilkan semua kombinasi yang mungkin (dan menghapus kombinasi kosong) dengan menemukan set daya input.

Untuk setiap kombinasi yang dihasilkan, kami menemukan persimpangan set dalam kombinasi, dan memfilter elemen yang ada di set lainnya.

m-@Fds-Qdty  input as Q
          y  power set
         t   remove the first one (empty combination)
m            for each combination d:
  @Fd            find the intersection of all the sets in d
 -               filter out those who are in
     s               the union of
      -Qd            the sets not in the combination
                     (input minus combination)

JavaScript (ES6), 123 byte

a=>a.map((b,i)=>b.map(e=>m[e]|=1<<i),m=[])&&[...Array(1<<a.length)].map((_,i)=>m.map((e,j)=>e==i&&j).filter(j=>j)).slice(1)