Buat set terpisah tanpa mengosongkannya

8

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.

fred russell
sumber
Jika tidak masuk akal maka mengapa mereka memahaminya di sini dreamincode.net/forums/topic/…
fred russell
@ Fredrussell mungkin, mungkin saja, ini tentang bagaimana Anda menjelaskannya, dan bukan tentang, misalnya notasi pada gambar?
NieDzejkob
7
@Fredrussell, penjelasan Anda tentang "tantangan" tidak jelas dan tidak diformat. Di situs ini biasanya Anda akan menemukan pertanyaan yang diformat dan diurutkan dengan benar, misalnya mengikuti tata letak seperti "Input; Output; Aturan; Testcases", tetapi Anda tidak memberikan apa pun tentang itu. Selain itu, Anda tidak memiliki kriteria kemenangan yang dapat menentukan pemenang. Dan setelah penghinaan Anda, saya tidak berpikir ada orang yang mau menyelesaikan pertanyaan sekarang. Bahkan di SO, Anda harus selalu ingat bahwa orang-orang yang menjawab melakukan ini di waktu luang mereka, jadi Anda tidak boleh kasar seperti itu.
Luca H
1
@Arnauld tercepat-kode akan menyiratkan bahwa jika kami berdua menulis O (n) algoritma, tetapi Anda adalah 100 kali lebih cepat, maka Anda menang. Jika kita hanya memerlukan kompleksitas waktu yang optimal, maka tidak apa-apa jika kode saya 100 kali lebih lambat, asalkan lebih kecil satu byte. Tetapi tantangan ini mungkin dianggap sebagai algoritma tercepat .
Misha Lavrov
2
Ini persis masalah menemukan pencocokan penuh dalam grafik bipartit. Kompleksitas waktu dari algoritma yang paling dikenal tergantung pada seberapa besar set dibandingkan dengan jumlah set. Tantangan terkait.
Zgarb

Jawaban:

2

Jelly , 8 byte

Œp⁼Q$ÐfḢ

Cobalah online!

Penjelasan

Œp⁼Q$ÐfḢ  Main Link
Œp        Cartesian Product of the elements; all possible lists
     Ðf   Filter; keep elements that are
  ⁼Q$     Equal to themselves uniquified
      Ḣ   Take the first one

Sangat tidak efisien. Asimptotik ϴ(n^(n+1))menurut Misha Lavrov; Saya pikir itu benar.

HyperNeutrino
sumber
Saya pikir ini setidaknya Ω (n ^ n): ukuran maksimum yang mungkin dari produk Cartesian.
Misha Lavrov
Lebih tepatnya, ϴ (n ^ (n + 1)), karena tanda centang "sama dengan sendiri uniquified" harus ϴ (n) waktu.
Misha Lavrov
@MishaLavrov Ah oke, terima kasih.
HyperNeutrino
@HyperNeutrino uniqueberfungsi di Jelly use O(n)containment ( x in s) periksa, masing-masing harus mengambil O(n)sesuai dengan halaman ini , jadi Qharus mengambil O(n^2)kasus terburuk / rata-rata waktu kasus kompleksitas. Oleh karena itu algoritma ini O(n^(n+2)). (unik dapat O(n)dalam kasus semua elemen sama, di mana setiap pemeriksaan kontainmenjalankan di O(1)) --- Pada catatan yang tidak terkait, dimungkinkan untuk menerapkan uniquedalam O(n)menggunakan setstruktur data Python builtin data yang hash-set. Pokoknya Jelly tidak dirancang untuk menjadi efisien.
user202729
2

Bahasa Wolfram (Mathematica) , 87 byte dan ϴ (n 3 )

-Range[n=Length@#]/.Rule@@@FindIndependentEdgeSet[Join@@Table[-i->j,{i,n},{j,#[[i]]}]]&

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-elemennya 1,2,...,n, dengan ujung dari -isampai jkapan jterkandung dalam ihimpunan -th. Temukan kecocokan sempurna dalam grafik ini menggunakan bawaan. Kemudian buatlah daftar elemen yang sesuai -1,-2,...,-ndalam urutan itu dalam pencocokan sempurna.

Mathematica FindIndependentEdgeSetadalah 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 ).

Misha Lavrov
sumber
Yah ... Mathematica buruk dalam kompleksitas terbatas , bukan untuk pertama kalinya.
user202729
2

Haskell , 48 byte

-1 byte terima kasih kepada nimi.

import Data.List
head.filter((==)<*>nub).mapM id

Cobalah online!

benar-benar manusiawi
sumber
2
mapM idbukannyasequence
nimi
1

Mathematica 39 Bytes

Last@Union[DeleteDuplicates/@Tuples@#]&

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:

(For[x={1,1},!DuplicateFreeQ@x,x=RandomChoice/@#];x)&

Sulit mengatakan mana yang benar-benar lebih cepat tanpa mengetahui sifat-sifat input yang mungkin.

Kelly Lowder
sumber
2
The DeleteDuplicates /@ Tuples@#Langkah mengambil Θ (n ^ (n + 1)) waktu dengan argumen yang sama seperti pada solusi lain. Kemudian Unionmemiliki 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).
Misha Lavrov
Saya pikir masalah ini memerlukan definisi multivariat dari notasi O besar untuk memiliki makna praktis. Jelas bahwa panjang sublists sangat penting.
Kelly Lowder
1
Interpretasi saya terhadap pernyataan masalah adalah bahwa hanya ketergantungan pada n (jumlah sublists) yang penting, dan kami mengasumsikan kasus terburuk tentang panjang sublists. Bagaimanapun, bahkan jika setiap sublist memiliki panjang 2, Tuples@#memiliki ukuran 2 ^ n, jadi perkiraan asimptotik pertama Anda tidak mungkin benar.
Misha Lavrov
Hah? Mengapa multivarian BigO bermasalah? Itu dilakukan sepanjang waktu.
user202729
1

05AB1E , 13 byte, O (n! * N)

āœʒ‚øε`QO}P}н

Cobalah online! Penjelasan:

ā               Make a range 1..n
 œ              Generate all permutations
  ʒ        }    Filter
   ‚ø           Zip with input
     ε   }      Loop over sets
      `QO       Check each element for membership
          P     All sets must match
            н   Take the first result
Neil
sumber
1

Sekam , 5 byte

►oLuΠ

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

►(Lu)Π  -- input as a list of lists, for example: [[1,2],[1,3],[1,4],[3,4]]
     Π  -- cartesian product: [[1,1,1,3],...,[2,3,4,4]]
►(  )   -- maximum by the following function (eg. on [1,1,1,3]):
   u    --   deduplicate: [1,3]
  L     --   length: 2
ბიმო
sumber
0

Pyth , 9 byte (ϴ (n n + 1 ))

Karena ini berfungsi persis seperti solusi Jelly, kemungkinan besar memiliki kompleksitas yang sama.

h{I#.nM*F

Coba di sini!

Bagaimana?

h {I # .nM * F | Program lengkap.

       * F | Lipat produk Cartesian.
    .nM | Ratakan masing-masing.
   # | Simpan itu:
 {I Itu berbeda dari penghapusan elemen duplikat.
h | Ambil elemen pertama.
Tuan Xcoder
sumber
0

JavaScript (ES6), 74 73 byte

1 byte disimpan, terima kasih kepada @Neil.

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

Berulang secara berulang melalui array mencari solusi.

Tidak Disatukan:

f=(
   [a, ...A],                        //a is the first array, A is the rest
   s = [],                           //s is the current trial solution
   S                                 //S holds the solution (if one exists) at this branch
  )=>
     a ? a.map(                      //if we're not done, iterate through a
           c => s.includes(c) ||     //  if this element already exists, short-circuit
                (S = S ||            //  else if S has a solution, keep it
                 f(A, [...s, c])     //  else look for a solution down this branch
                )
         ) && S                      //return S

Kasus uji:

Rick Hitchcock
sumber
Kenapa tidak a?a.map(... )&&S:s?
Neil
@Neil, karena Duh. Terima kasih!
Rick Hitchcock
0

Python3, 93 84 byte

-9 byte berkat caird coinheringaahing

lambda I:next(filter(lambda x:len(x)==len({*x}),product(*I)))
from itertools import*

Cobalah online!

Setop
sumber
1
84 byte
caird coinheringaahing