Misalkan Anda memiliki satu set himpunan bilangan bulat. Mungkin saja beberapa set akan tumpang tindih (mis. Elemen berbagi). Anda bisa menghilangkan tumpang tindih dengan menghapus elemen dari set, tetapi beberapa dari mereka mungkin berakhir kosong; itu akan memalukan. Bisakah kita membuat semua set terpisah tanpa mengosongkannya?
Perhatikan bahwa dalam situasi ini, tidak pernah ada alasan untuk meninggalkan beberapa elemen dalam satu set, sehingga masalah ini selalu dapat diselesaikan dengan mengurangi setiap set menjadi hanya satu elemen. Itulah versi masalah yang kami selesaikan di sini.
Tugas
Tulis program atau fungsi, sebagai berikut:
Input : Daftar set bilangan bulat.
Output : Daftar bilangan bulat, dengan panjang yang sama dengan input, untuk yang:
- Semua bilangan bulat dalam output berbeda; dan
- Setiap integer dalam output adalah elemen dari set input yang sesuai.
Klarifikasi
- Anda dapat mewakili satu set sebagai daftar jika Anda ingin (atau apa pun yang sesuai untuk bahasa Anda), mengabaikan urutan elemen.
- Anda tidak harus menangani kasus di mana tidak ada solusi (yaitu akan selalu ada setidaknya satu solusi).
- Mungkin ada lebih dari satu solusi. Algoritme Anda harus selalu menghasilkan solusi yang valid, tetapi diizinkan untuk tidak deterministik (artinya tidak masalah jika mengambil solusi valid yang berbeda setiap kali berjalan).
- Jumlah bilangan bulat berbeda yang muncul dalam input, n , akan sama dengan jumlah set dalam input, dan untuk kesederhanaan, akan menjadi bilangan bulat dari 1 hingga n inklusif (karena nilai aktualnya tidak masalah). Terserah Anda apakah Anda ingin mengeksploitasi fakta ini atau tidak.
Testcases
[{1,2},{1,3},{1,4},{3,4}] -> [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -> [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -> [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]
Kondisi kemenangan
Suatu program membutuhkan kompleksitas waktu yang optimal untuk menang, yaitu jika suatu algoritma dengan kompleksitas waktu yang lebih baik ditemukan, itu mendiskualifikasi semua entri yang lebih lambat. (Anda dapat mengasumsikan bahwa bawaan bahasa Anda berjalan secepat mungkin, misalnya Anda dapat mengasumsikan bahwa bawaan penyortiran berjalan dalam waktu O (n log n). Demikian juga, asumsikan bahwa semua bilangan bulat dengan ukuran yang sebanding dengan n dapat ditambahkan, dikalikan, dll. (dalam waktu yang konstan.)
Karena kompleksitas waktu yang optimal kemungkinan cukup mudah diperoleh dalam sebagian besar bahasa, maka pemenang akan menjadi program terpendek di antara mereka yang memiliki kompleksitas waktu pemenang, diukur dalam byte.
sumber
Jawaban:
Jelly , 8 byte
Cobalah online!
Penjelasan
Sangat tidak efisien. Asimptotik
ϴ(n^(n+1))
menurut Misha Lavrov; Saya pikir itu benar.sumber
unique
berfungsi di Jelly useO(n)
containment (x in s
) periksa, masing-masing harus mengambilO(n)
sesuai dengan halaman ini , jadiQ
harus mengambilO(n^2)
kasus terburuk / rata-rata waktu kasus kompleksitas. Oleh karena itu algoritma iniO(n^(n+2))
. (unik dapatO(n)
dalam kasus semua elemen sama, di mana setiap pemeriksaan kontainmenjalankan diO(1)
) --- Pada catatan yang tidak terkait, dimungkinkan untuk menerapkanunique
dalamO(n)
menggunakanset
struktur data Python builtin data yang hash-set. Pokoknya Jelly tidak dirancang untuk menjadi efisien.Bahasa Wolfram (Mathematica) , 87 byte dan ϴ (n 3 )
Cobalah online!
Membangun grafik bipartit yang simpul-simpulnya di satu sisi adalah himpunan (diindeks oleh
-1,-2,...,-n
) dan simpul-simpulnya di sisi yang lain adalah elemen-elemennya1,2,...,n
, dengan ujung dari-i
sampaij
kapanj
terkandung dalami
himpunan -th. Temukan kecocokan sempurna dalam grafik ini menggunakan bawaan. Kemudian buatlah daftar elemen yang sesuai-1,-2,...,-n
dalam urutan itu dalam pencocokan sempurna.Mathematica
FindIndependentEdgeSet
adalah hambatan di sini; yang lain membutuhkan O (n 2 ) operasi untuk dilakukan. Mathematica mungkin menggunakan algoritma Hungaria , dan jadi saya akan berasumsi bahwa itu berjalan dalam waktu ϴ (n 3 ) , meskipun ada kemungkinan bahwa Mathematica memiliki implementasi yang naif dengan kompleksitas O (n 4 ).sumber
Haskell , 48 byte
-1 byte terima kasih kepada nimi.
Cobalah online!
sumber
mapM id
bukannyasequence
Mathematica 39 Bytes
Pada masalah kompleksitas, saya pikir ini sangat tergantung pada panjang masing-masing sublist, serta ukuran seberapa terpisah sublists.
Jadi, saya pikir algoritma ini adalah O (n Log n + n ^ 2 Log m) di mana m kira-kira panjang rata-rata setiap sublist.
Sesuatu seperti ini akan memiliki kompleksitas O (a ^ n) di mana a> 1 adalah ukuran dari tumpang tindih dalam sublists:
Sulit mengatakan mana yang benar-benar lebih cepat tanpa mengetahui sifat-sifat input yang mungkin.
sumber
DeleteDuplicates /@ Tuples@#
Langkah mengambil Θ (n ^ (n + 1)) waktu dengan argumen yang sama seperti pada solusi lain. KemudianUnion
memiliki daftar panjang n ^ n untuk disortir, yang membutuhkan O (n ^ (n + 1) log (n)) waktu - tetapi mungkin lebih cepat karena paling banyak 2 ^ nn! elemen dalam daftar itu berbeda. Either way, kompleksitasnya adalah ϴ (n ^ (n + 1)) hingga faktor log (n).Tuples@#
memiliki ukuran 2 ^ n, jadi perkiraan asimptotik pertama Anda tidak mungkin benar.05AB1E , 13 byte, O (n! * N)
Cobalah online! Penjelasan:
sumber
Sekam , 5 byte
Cobalah online!
Penjelasan
Hanya melihat hal tentang kompleksitas: Seperti yang sering terjadi dengan solusi bahasa golf, mereka tidak terlalu efisien - yang ini memiliki kompleksitas O (n · nⁿ).
sumber
Pyth , 9 byte (ϴ (n n + 1 ))
Karena ini berfungsi persis seperti solusi Jelly, kemungkinan besar memiliki kompleksitas yang sama.
Coba di sini!
Bagaimana?
sumber
JavaScript (ES6),
7473 byte1 byte disimpan, terima kasih kepada @Neil.
Berulang secara berulang melalui array mencari solusi.
Tidak Disatukan:
Kasus uji:
Tampilkan cuplikan kode
sumber
a?a.map(
...)&&S:s
?Python3,
9384 byte-9 byte berkat caird coinheringaahing
Cobalah online!
sumber