Kemarin saya memasangkan kaus kaki dari binatu dan menemukan cara saya melakukannya sangat tidak efisien. Saya sedang melakukan pencarian naif - mengambil satu kaus kaki dan "iterasi" tumpukan untuk menemukan pasangannya. Hal ini memerlukan iterasi n / 2 * n / 4 = n ² /8 kaus kaki rata-rata.

Sebagai seorang ilmuwan komputer saya berpikir apa yang bisa saya lakukan? Penyortiran (sesuai ukuran / warna / ...) tentu saja terlintas dalam pikiran untuk mencapai solusi O (NlogN).

Hashing atau solusi tidak-di-tempat lainnya bukanlah suatu pilihan, karena saya tidak dapat menduplikasi kaus kaki saya (walaupun mungkin lebih baik jika saya bisa).

Jadi, pertanyaannya pada dasarnya:

Diberikan tumpukan nkaus kaki, berisi 2nelemen (anggap setiap kaus kaki memiliki tepat satu pasangan yang cocok), apa cara terbaik untuk memasangkan mereka secara efisien hingga ruang ekstra logaritmik? (Saya yakin saya bisa mengingat jumlah info itu jika diperlukan.)

Saya akan menghargai jawaban yang membahas aspek-aspek berikut:

• Solusi teoretis umum untuk sejumlah besar kaus kaki.
• Jumlah kaus kaki sebenarnya tidak terlalu besar, saya tidak percaya pasangan saya dan saya memiliki lebih dari 30 pasang. (Dan itu cukup mudah untuk membedakan antara kaus kakiku dan miliknya; bisakah ini digunakan juga?)
• Apakah ini setara dengan masalah perbedaan elemen ?

Solusi pengurutan telah diusulkan, tetapi pengurutan agak terlalu banyak : Kami tidak perlu memesan; kita hanya perlu kelompok kesetaraan .

Jadi hashing sudah cukup (dan lebih cepat).

1. Untuk setiap warna kaus kaki, bentuk tumpukan . Iterasi semua kaus kaki dalam keranjang input Anda dan bagikan ke tumpukan warna .
2. Ulangi setiap tumpukan dan distribusikan dengan beberapa metrik lain (misalnya pola) ke dalam tumpukan kedua
3. Terapkan skema ini secara rekursif sampai Anda telah mendistribusikan semua kaus kaki ke tumpukan yang sangat kecil yang dapat Anda proses secara visual segera

Jenis partisi hash rekursif ini sebenarnya dilakukan oleh SQL Server ketika perlu menggabungkan hash atau agregat hash atas kumpulan data besar. Ini mendistribusikan aliran input build-nya ke banyak partisi yang independen. Skema ini menskala ke jumlah data acak dan banyak CPU secara linier.

Anda tidak perlu mempartisi secara rekursif jika Anda dapat menemukan kunci distribusi (kunci hash) yang menyediakan cukup banyak bucket sehingga setiap bucket cukup kecil untuk diproses dengan sangat cepat. Sayangnya, saya tidak berpikir kaus kaki memiliki properti seperti itu.

Jika setiap kaus kaki memiliki bilangan bulat yang disebut "PairID" orang dapat dengan mudah mendistribusikannya ke dalam 10 ember sesuai dengan PairID % 10(digit terakhir).

Partisi dunia nyata terbaik yang dapat saya pikirkan adalah membuat persegi panjang tumpukan : satu dimensi adalah warna, yang lain adalah polanya. Mengapa persegi panjang? Karena kita membutuhkan O (1) akses acak ke tumpukan. ( Kubus 3D juga bisa digunakan, tapi itu tidak terlalu praktis.)

Memperbarui:

Bagaimana dengan paralelisme ? Bisakah beberapa manusia cocok dengan kaus kaki lebih cepat?

1. Strategi paralelisasi yang paling sederhana adalah meminta banyak pekerja mengambil dari keranjang input dan meletakkan kaus kaki ke tumpukan. Ini hanya bertambah banyak - bayangkan 100 orang bertarung lebih dari 10 tumpukan. Biaya sinkronisasi (memanifestasikan diri sebagai tabrakan tangan dan komunikasi manusia) menghancurkan efisiensi dan percepatan (lihat Hukum Skalabilitas Universal !). Apakah ini rentan terhadap kebuntuan ? Tidak, karena setiap pekerja hanya perlu mengakses satu tumpukan pada satu waktu. Hanya dengan satu "kunci" tidak mungkin ada jalan buntu. Livelocks mungkin dimungkinkan tergantung pada bagaimana manusia mengoordinasikan akses ke tumpukan. Mereka mungkin hanya menggunakan backoff acakseperti kartu jaringan melakukan itu pada tingkat fisik untuk menentukan kartu apa yang secara eksklusif dapat mengakses kawat jaringan. Jika bekerja untuk NIC , itu harus bekerja untuk manusia juga.
2. Ia bersisik hampir tanpa batas jika setiap pekerja memiliki tumpukan tiangnya sendiri . Pekerja kemudian dapat mengambil potongan besar kaus kaki dari keranjang input (sangat sedikit pertengkaran karena mereka jarang melakukannya) dan mereka tidak perlu menyinkronkan ketika mendistribusikan kaus kaki sama sekali (karena mereka memiliki tumpukan benang lokal). Pada akhirnya, semua pekerja harus menyatukan tumpukan mereka. Saya percaya itu dapat dilakukan dalam O (log (jumlah pekerja * tumpukan per pekerja)) jika pekerja membentuk pohon agregasi .

Bagaimana dengan masalah perbedaan elemen ? Seperti yang dinyatakan dalam artikel, masalah perbedaan elemen dapat diselesaikan O(N). Ini sama untuk masalah kaus kaki (juga O(N), jika Anda hanya memerlukan satu langkah distribusi (saya mengusulkan beberapa langkah hanya karena manusia buruk dalam perhitungan - satu langkah sudah cukup jika Anda distribusikan md5(color, length, pattern, ...), yaitu hash sempurna dari semua atribut)).

Jelas, seseorang tidak bisa pergi lebih cepat daripada O(N), jadi kami telah mencapai batas bawah optimal .

Meskipun keluarannya tidak persis sama (dalam satu kasus, hanya boolean. Dalam kasus lain, pasangan kaus kaki), kompleksitas asimptotiknya sama.

Karena arsitektur otak manusia sama sekali berbeda dari CPU modern, pertanyaan ini tidak masuk akal secara praktis.

Manusia dapat menang atas algoritma CPU menggunakan fakta bahwa "menemukan pasangan yang cocok" dapat menjadi satu operasi untuk satu set yang tidak terlalu besar.

Algoritme saya:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

Setidaknya inilah yang saya gunakan dalam kehidupan nyata, dan saya merasa sangat efisien. Kelemahannya adalah membutuhkan permukaan yang rata, tetapi biasanya berlimpah.

Kasus 1 : Semua kaus kaki identik (ini yang saya lakukan di kehidupan nyata).

Pilih salah satu dari mereka untuk membuat pasangan. Waktu yang konstan.

Kasus 2 : Ada jumlah kombinasi yang konstan (kepemilikan, warna, ukuran, tekstur, dll.).

Gunakan jenis radix . Ini hanya waktu linear karena perbandingan tidak diperlukan.

Kasus 3 : Jumlah kombinasi tidak diketahui sebelumnya (kasus umum).

Kita harus melakukan perbandingan untuk memeriksa apakah dua kaus kaki berpasangan. Pilih salah satu O(n log n)algoritma pengurutan berbasis perbandingan.

Namun dalam kehidupan nyata ketika jumlah kaus kaki relatif kecil (konstan), algoritma yang optimal secara teoritis ini tidak akan bekerja dengan baik. Mungkin butuh lebih banyak waktu daripada pencarian berurutan, yang secara teoritis membutuhkan waktu kuadratik.

Jawaban non-algoritmik, namun "efisien" ketika saya melakukannya:

• langkah 1) buang semua kaus kaki yang ada

• langkah 2) pergi ke Walmart dan membelinya dengan paket paket 10 - n putih dan paket m hitam. Tidak perlu warna lain dalam kehidupan sehari-hari.

Namun berkali-kali, saya harus melakukan ini lagi (kehilangan kaus kaki, kaus kaki rusak, dll), dan saya benci terlalu sering membuang kaus kaki yang baik (dan saya berharap mereka terus menjual referensi kaus kaki yang sama!), Jadi saya baru-baru ini mengambil pendekatan yang berbeda.

Jawaban algoritmik:

Pertimbangkan daripada jika Anda hanya menggambar satu kaus kaki untuk tumpukan kaus kaki kedua, seperti yang Anda lakukan, peluang Anda untuk menemukan kaus kaki yang cocok dalam pencarian naif cukup rendah.

• Jadi ambil lima dari mereka secara acak, dan hafalkan bentuk atau panjangnya.

Kenapa lima? Biasanya manusia baik mengingat antara lima dan tujuh elemen berbeda dalam memori yang bekerja - agak mirip dengan manusia yang setara dengan tumpukan RPN - lima adalah standar yang aman.

• Ambil satu dari tumpukan 2n-5.

• Sekarang cari korek api (pencocokan pola visual - manusia bagus dalam hal itu dengan tumpukan kecil) di dalam lima yang Anda gambar, jika Anda tidak menemukan satu, maka tambahkan ke lima Anda.

• Tetap ambil kaus kaki secara acak dari tumpukan dan bandingkan dengan kaus kaki 5 +1 Anda untuk pertandingan. Seiring tumpukan Anda tumbuh, itu akan mengurangi kinerja Anda tetapi meningkatkan peluang Anda. Lebih cepat.

Jangan ragu untuk menuliskan formula untuk menghitung berapa banyak sampel yang harus Andaundi untuk peluang 50% pertandingan. IIRC itu adalah hukum hypergeometric.

Saya melakukan itu setiap pagi dan jarang membutuhkan lebih dari tiga kali imbang - tetapi saya memiliki npasangan serupa (sekitar 10, memberi atau mengambil yang hilang) dari mkaus kaki putih berbentuk. Sekarang Anda dapat memperkirakan ukuran tumpukan stok saya :-)

BTW , saya menemukan bahwa jumlah biaya transaksi untuk menyortir semua kaus kaki setiap kali saya membutuhkan sepasang jauh lebih sedikit daripada melakukannya sekali dan mengikat kaus kaki. Just-in-time bekerja lebih baik karena Anda tidak perlu mengikat kaus kaki, dan ada juga pengembalian marjinal yang semakin berkurang (yaitu, Anda terus mencari dua atau tiga kaus kaki itu ketika di suatu tempat di binatu dan yang Anda butuhkan untuk menyelesaikan pencocokan kaus kaki Anda dan Anda kehilangan waktu untuk itu).

Apa yang saya lakukan adalah saya mengambil kaus kaki pertama dan meletakkannya (katakanlah, di tepi mangkuk cucian). Kemudian saya mengambil kaus kaki lain dan memeriksa apakah kaus kaki itu sama dengan kaus kaki pertama. Jika ya, saya menghapus keduanya. Jika tidak, saya letakkan di sebelah kaus kaki pertama. Lalu saya mengambil kaus kaki ketiga dan membandingkannya dengan dua yang pertama (jika masih ada). Dll

Pendekatan ini dapat dengan mudah diimplementasikan dalam sebuah array, dengan asumsi bahwa "menghapus" kaus kaki adalah sebuah opsi. Sebenarnya, Anda bahkan tidak perlu "melepas" kaus kaki. Jika Anda tidak perlu menyortir kaus kaki (lihat di bawah), maka Anda bisa memindahkannya dan berakhir dengan array yang mengatur semua kaus kaki berpasangan dalam array.

Dengan asumsi bahwa satu-satunya operasi untuk kaus kaki adalah untuk membandingkan kesetaraan, algoritma ini pada dasarnya masih merupakan algoritma n ² , meskipun saya tidak tahu tentang kasus rata-rata (tidak pernah belajar menghitung itu).

Penyortiran, tentu saja meningkatkan efisiensi, terutama dalam kehidupan nyata di mana Anda dapat dengan mudah "memasukkan" kaus kaki di antara dua kaus kaki lainnya. Dalam komputasi hal yang sama dapat dicapai oleh pohon, tapi itu ruang ekstra. Dan, tentu saja, kita kembali ke NlogN (atau sedikit lebih, jika ada beberapa kaus kaki yang sama dengan kriteria pengurutan, tetapi tidak dari pasangan yang sama).

Selain itu, saya tidak bisa memikirkan apa pun, tetapi metode ini tampaknya cukup efisien dalam kehidupan nyata. :)

Ini mengajukan pertanyaan yang salah. Pertanyaan yang tepat untuk ditanyakan adalah, mengapa saya menghabiskan waktu menyortir kaus kaki? Berapa biayanya setiap tahun, ketika Anda menghargai waktu luang Anda untuk unit moneter X pilihan Anda?

Dan lebih sering daripada tidak, ini bukan sembarang waktu luang, ini adalah waktu luang pagi , yang bisa Anda habiskan di tempat tidur, atau menyeruput kopi Anda, atau pergi sedikit lebih awal dan tidak terjebak dalam lalu lintas.

Seringkali baik untuk mengambil langkah mundur, dan memikirkan jalan keluar masalahnya.

Dan ada caranya!

Temukan kaus kaki yang kamu suka. Mempertimbangkan semua fitur yang relevan: warna dalam kondisi pencahayaan yang berbeda, kualitas dan daya tahan keseluruhan, kenyamanan dalam kondisi iklim yang berbeda, dan penyerapan bau. Juga penting adalah, mereka tidak boleh kehilangan elastisitas dalam penyimpanan, sehingga kain alami bagus, dan mereka harus tersedia dalam pembungkus plastik.

Lebih baik jika tidak ada perbedaan antara kaus kaki kiri dan kanan, tetapi itu tidak penting. Jika kaus kaki kiri-kanan simetris, menemukan pasangan adalah operasi O (1), dan menyortir kaus kaki adalah perkiraan dari operasi O (M), di mana M adalah jumlah tempat di rumah Anda, yang telah Anda serasi dengan kaus kaki, idealnya beberapa angka konstan kecil.

Jika Anda memilih pasangan mewah dengan kaus kaki kiri dan kanan yang berbeda, lakukan penyortiran ember penuh untuk ember kiri dan kanan, ambil O (N + M), dengan N adalah jumlah kaus kaki dan M sama seperti di atas. Orang lain dapat memberikan rumus untuk iterasi rata-rata menemukan pasangan pertama, tetapi kasus terburuk untuk menemukan pasangan dengan pencarian buta adalah N / 2 + 1, yang menjadi kasus astronomi yang tidak mungkin untuk N. yang masuk akal. Hal ini dapat dipercepat dengan menggunakan gambar lanjutan algoritma pengenalan dan heuristik, saat memindai tumpukan kaus kaki yang tidak disortir dengan Mk1 Eyeball .

Jadi, sebuah algoritma untuk mencapai efisiensi pemasangan kaus kaki O (1) (dengan asumsi kaus kaki simetris) adalah:

1. Anda perlu memperkirakan berapa pasang kaus kaki yang akan Anda butuhkan selama sisa hidup Anda, atau mungkin sampai Anda pensiun dan pindah ke iklim yang lebih hangat tanpa perlu memakai kaus kaki lagi. Jika Anda masih muda, Anda juga bisa memperkirakan berapa lama sebelum kita semua memiliki robot pemilahan kaus kaki di rumah kita, dan seluruh masalah menjadi tidak relevan.

2. Anda perlu mengetahui bagaimana Anda dapat memesan kaus kaki yang Anda pilih dalam jumlah besar, dan berapa biayanya, dan apakah mereka mengirimkannya.

3. Pesan kaus kaki!

4. Singkirkan kaus kaki lama Anda.

Langkah alternatif 3 akan melibatkan membandingkan biaya membeli jumlah yang sama dari kaus kaki yang mungkin lebih murah beberapa pasang sekaligus selama bertahun-tahun dan menambahkan biaya menyortir kaus kaki, tetapi ambil kata saya untuk itu: membeli dalam jumlah besar lebih murah! Juga, kaus kaki dalam penyimpanan meningkatkan nilai pada tingkat inflasi harga saham, yang lebih banyak daripada yang Anda dapatkan dari banyak investasi. Kemudian lagi ada juga biaya penyimpanan, tetapi kaus kaki benar-benar tidak memakan banyak ruang di rak paling atas lemari.

Masalah terpecahkan. Jadi, dapatkan kaus kaki baru, buang / sumbangkan yang lama Anda, dan hidup bahagia selamanya setelah mengetahui Anda menabung uang dan waktu setiap hari selama sisa hidup Anda.

Batas teoretisnya adalah O (n) karena Anda harus menyentuh setiap kaus kaki (kecuali beberapa sudah dipasangkan entah bagaimana).

Anda dapat mencapai O (n) dengan jenis radix . Anda hanya perlu memilih beberapa atribut untuk ember.

1. Pertama, Anda dapat memilih (miliknya, milikku) - membaginya menjadi 2 tumpukan,
2. kemudian gunakan warna (dapat memiliki urutan warna apa saja, misalnya menurut abjad berdasarkan nama warna) - pisahkan menjadi tumpukan berdasarkan warna (ingat untuk menjaga urutan awal dari langkah 1 untuk semua kaus kaki dalam tumpukan yang sama),
3. lalu panjang kaus kaki itu,
4. lalu ....

Jika Anda dapat memilih sejumlah atribut, tetapi cukup atribut yang dapat secara unik mengidentifikasi setiap pasangan, Anda harus melakukan dalam O (k * n), yaitu O (n) jika kita dapat menganggap k terbatas.

Sebagai solusi praktis:

1. Membuat tumpukan kaus kaki yang mudah dibedakan dengan cepat. (Katakan dengan warna)
2. Quicksort setiap tumpukan dan gunakan panjang kaus kaki untuk perbandingan. Sebagai manusia, Anda dapat membuat keputusan yang cukup cepat yang digunakan untuk partisi yang menghindari kasus terburuk. (Anda dapat melihat banyak kaus kaki secara paralel, gunakan itu untuk keuntungan Anda!)
3. Hentikan penyortiran tumpukan ketika mereka mencapai ambang di mana Anda merasa nyaman untuk menemukan pasangan spot dan kaus kaki yang tidak dapat disambungkan secara instan

Jika Anda memiliki 1000 kaus kaki, dengan 8 warna dan distribusi rata-rata, Anda dapat membuat 4 tumpukan masing-masing 125 kaus kaki dalam waktu c * n. Dengan ambang 5 kaus kaki, Anda dapat mengurutkan setiap tumpukan dalam 6 langkah. (Menghitung 2 detik untuk melempar kaus kaki di tumpukan kanan akan membuat Anda sedikit di bawah 4 jam.)

Jika Anda hanya memiliki 60 kaus kaki, 3 warna, dan 2 jenis kaus kaki (milik Anda / istri Anda), Anda dapat mengurutkan setiap tumpukan 10 kaus kaki dalam 1 kali jalan (Sekali lagi ambang = 5). (Menghitung 2 detik akan memakan waktu 2 menit).

Penyortiran bucket awal akan mempercepat proses Anda, karena memecah kaus kaki menjadi ember dalam c*nwaktu sehingga Anda hanya perlu melakukan c*n*log(k)pekerjaan. (Tidak memperhitungkan ambang batas). Jadi semuanya Anda lakukan tentang n*c*(1 + log(k))pekerjaan, di mana c adalah waktu untuk melemparkan kaus kaki di atas tumpukan.

Pendekatan ini akan lebih baik dibandingkan dengan c*x*n + O(1)metode apa pun selama ini log(k) < x - 1.

Dalam ilmu komputer ini dapat membantu: Kami memiliki koleksi n hal , urutannya (panjang) dan juga hubungan ekivalensi (informasi tambahan, misalnya warna kaus kaki). Relasi ekivalensi memungkinkan kita untuk membuat partisi dari koleksi asli, dan di setiap kelas ekivalensi order kita tetap dipertahankan. Pemetaan sesuatu untuk kelas ekivalensi itu dapat dilakukan dalam O (1), jadi hanya O (n) yang diperlukan untuk menetapkan setiap item ke suatu kelas. Sekarang kami telah menggunakan informasi tambahan kami dan dapat melanjutkan dengan cara apa pun untuk menyortir setiap kelas. Keuntungannya adalah set data sudah jauh lebih kecil.

Metode ini juga dapat disarangkan, jika kita memiliki beberapa hubungan ekivalensi -> membuat tumpukan warna, daripada di setiap partisi tumpukan pada tekstur, daripada mengurutkan panjang. Setiap relasi ekivalensi yang menciptakan partisi dengan lebih dari 2 elemen yang memiliki ukuran genap akan membawa peningkatan kecepatan pada penyortiran (asalkan kita dapat secara langsung menetapkan kaus kaki pada tumpukannya), dan penyortiran dapat terjadi dengan sangat cepat pada set data yang lebih kecil.

Anda mencoba menyelesaikan masalah yang salah.

Solusi 1: Setiap kali Anda memasukkan kaus kaki kotor ke keranjang cucian Anda, ikat dengan simpul kecil. Dengan begitu Anda tidak perlu melakukan penyortiran setelah pencucian. Anggap saja seperti mendaftarkan indeks dalam database Mongo. Sedikit pekerjaan di depan untuk penghematan CPU di masa depan.

Solusi 2: Jika musim dingin, Anda tidak harus mengenakan kaus kaki yang serasi. Kami adalah programmer. Tidak ada yang perlu tahu, selama itu berhasil.

Solusi 3: Sebarkan pekerjaan. Anda ingin melakukan proses CPU yang sedemikian rumit secara asinkron, tanpa memblokir UI. Ambil tumpukan kaus kaki itu dan masukkan ke dalam tas. Hanya mencari pasangan saat Anda membutuhkannya. Dengan begitu jumlah pekerjaan yang dibutuhkan jauh lebih sedikit terlihat.

Semoga ini membantu!

Pertanyaan ini sebenarnya sangat filosofis. Pada intinya ini tentang apakah kekuatan orang untuk memecahkan masalah ("perangkat basah" otak kita) setara dengan apa yang dapat dicapai oleh algoritma.

Algoritma yang jelas untuk menyortir kaus kaki adalah:

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

Sekarang ilmu komputer dalam masalah ini adalah tentang langkah-langkahnya

1. "Jika s berpasangan dengan kaus kaki t dalam N". Seberapa cepat kita bisa "mengingat" apa yang telah kita lihat sejauh ini?
2. "hapus t dari N" dan "tambahkan s ke N". Seberapa mahalnya melacak apa yang telah kita lihat sejauh ini?

Manusia akan menggunakan berbagai strategi untuk melakukan ini. Memori manusia bersifat asosiatif , seperti tabel hash di mana kumpulan fitur nilai yang disimpan dipasangkan dengan nilai yang sesuai sendiri. Misalnya, konsep "mobil merah" memetakan semua mobil merah yang mampu diingat oleh seseorang. Seseorang dengan ingatan sempurna memiliki pemetaan yang sempurna. Kebanyakan orang tidak sempurna dalam hal ini (dan sebagian besar lainnya). Peta asosiatif memiliki kapasitas terbatas. Pemetaan mungkin tertidur keluar dari keberadaan dalam berbagai keadaan (satu bir terlalu banyak), dicatat dalam kekeliruan ("Saya meskipun namanya Betty, bukan Nettie"), atau tidak pernah ditimpa walaupun kami mengamati bahwa kebenaran telah berubah ("mobil ayah" membangkitkan "oranye Firebird" ketika kita benar-benar tahu dia telah memperdagangkan itu untuk Camaro merah).

Dalam hal kaus kaki, penarikan kembali yang sempurna berarti melihat kaus kaki sselalu menghasilkan memori saudara kandungnya t, termasuk informasi yang cukup (di mana papan setrika) berada tdi waktu yang konstan. Seseorang dengan memori fotografis mencapai 1 dan 2 dalam waktu konstan tanpa gagal.

Seseorang dengan memori kurang sempurna mungkin menggunakan beberapa kelas kesetaraan akal sehat berdasarkan fitur dalam kemampuannya untuk melacak: ukuran (papa, mama, baby), warna (kehijauan, kemerahan, dll.), Pola (argyle, polos, dll.) , gaya (footie, setinggi lutut, dll.). Jadi papan setrika akan dibagi menjadi beberapa bagian untuk kategorinya. Ini biasanya memungkinkan kategori untuk ditempatkan dalam waktu yang konstan oleh memori, tetapi kemudian pencarian linear melalui kategori "ember" diperlukan.

Seseorang tanpa ingatan atau imajinasi sama sekali (maaf) hanya akan menyimpan kaus kaki dalam satu tumpukan dan melakukan pencarian linear dari seluruh tumpukan.

Orang aneh yang rapi mungkin menggunakan label numerik untuk pasangan seperti yang disarankan seseorang. Ini membuka pintu untuk pemesanan total, yang memungkinkan manusia untuk menggunakan algoritma yang persis sama dengan CPU: pencarian biner, pohon, hash, dll.

Jadi algoritme "terbaik" tergantung pada kualitas wetware / hardware / software yang menjalankannya dan kemauan kami untuk "menipu" dengan memaksakan urutan total pada pasangan. Tentu saja meta "terbaik" - algoritma adalah untuk menyewa penyortir kaus kaki terbaik dunia: seseorang atau mesin yang dapat memperoleh dan dengan cepat menyimpan sejumlah besar set atribut kaus kaki dalam memori asosiatif 1-1 dengan memori waktu konstan, menyisipkan, dan hapus. Baik orang dan mesin seperti ini dapat dibeli. Jika Anda memilikinya, Anda dapat memasangkan semua kaus kaki dalam waktu O (N) untuk pasangan N, yang optimal. Tag pesanan total memungkinkan Anda untuk menggunakan hashing standar untuk mendapatkan hasil yang sama dengan komputer manusia atau perangkat keras.

Biaya: Memindahkan kaus kaki -> tinggi, mencari / mencari kaus kaki sejalan -> kecil

Yang ingin kami lakukan adalah mengurangi jumlah gerakan, dan mengimbanginya dengan jumlah pencarian. Juga, kita dapat memanfaatkan lingkungan multithreded dari Homo Sapiens untuk menyimpan lebih banyak hal dalam cache keputusan.

X = Milikmu, Y = Pasanganmu

Dari tumpukan A dari semua kaus kaki:

Pilih dua kaus kaki, tempatkan kaus kaki X yang sesuai di jalur X, dan kaus kaki Y di jalur Y di posisi yang tersedia berikutnya.

Lakukan sampai A kosong.

Untuk setiap baris X dan Y

1. Pilih kaus kaki pertama di baris, cari di sepanjang baris sampai menemukan kaus kaki yang sesuai.

2. Masukkan ke dalam garis kaus kaki yang sudah jadi.

3. Opsional Saat Anda mencari garis dan dan kaus kaki saat ini yang Anda lihat identik dengan yang sebelumnya, lakukan langkah 2 untuk kaus kaki ini.

Secara opsional untuk langkah satu, Anda mengambil dua kaus kaki dari garis itu, bukan dua, karena memori caching cukup besar, kami dapat dengan cepat mengidentifikasi apakah kaus kaki cocok dengan yang ada di baris yang Anda amati. Jika Anda cukup beruntung memiliki tiga tangan, Anda mungkin dapat mengurai tiga kaus kaki pada saat yang sama mengingat memori subjek cukup besar.

Lakukan sampai X dan Y kosong.

Selesai

Namun, karena ini memiliki kompleksitas yang sama sebagai pemilihan, waktu yang dibutuhkan jauh lebih sedikit karena kecepatan I / O (kaus kaki bergerak) dan pencarian (mencari garis kaus kaki).

Berikut adalah Omega (n log n) batas bawah dalam model berbasis perbandingan. (Satu-satunya operasi yang valid adalah membandingkan dua kaus kaki.)

Misalkan Anda tahu bahwa kaus kaki 2n Anda diatur seperti ini:

p ₁ p ₂ p ₃ ... p _n p _{f (1)} p _{f (2)} ... p _{f (n)}

di mana f adalah permutasi yang tidak diketahui dari set {1,2, ..., n}. Mengetahui hal ini tidak akan membuat masalah menjadi lebih sulit. Ada n! kemungkinan hasil (pencocokan antara babak pertama dan kedua), yang berarti Anda perlu perbandingan log (n!) = Omega (n log n). Ini dapat diperoleh dengan menyortir.

Karena Anda tertarik pada koneksi ke masalah perbedaan elemen: membuktikan ikatan Omega (n log n) untuk perbedaan elemen lebih sulit, karena outputnya biner ya / tidak. Di sini, output harus sesuai dan jumlah output yang mungkin cukup untuk mendapatkan batas yang layak. Namun, ada varian yang terhubung dengan perbedaan elemen. Misalkan Anda diberi kaus kaki 2n dan bertanya-tanya apakah kaus kaki itu dapat dipasangkan secara unik. Anda bisa mendapatkan pengurangan dari ED dengan mengirimkan (a ₁ , a ₂ , ..., a _n ) untuk (a ₁ , a ₁ , a ₂ , a ₂ , ..., a _n , a _n ). (Secara parentetis, bukti kekerasan ED sangat menarik, melalui topologi.)

Saya pikir harus ada Omega (n ² ) yang terikat untuk masalah awal jika Anda mengizinkan tes kesetaraan saja. Intuisi saya adalah: Pertimbangkan grafik di mana Anda menambahkan tepi setelah tes, dan berpendapat bahwa jika grafik tidak padat hasilnya tidak ditentukan secara unik.

Inilah yang sebenarnya saya lakukan, untuk p pasang kaus kaki ( n = 2p kaus kaki individu):

• Ambil kaus kaki secara acak dari tumpukan.
• Untuk kaus kaki pertama, atau jika semua kaus kaki yang sebelumnya dipilih telah dipasangkan, cukup masukkan kaus kaki ke dalam "slot" pertama dari "susunan" kaus kaki tidak berpasangan di depan Anda.
• Jika Anda memiliki satu atau lebih kaus kaki tidak berpasangan yang dipilih, periksa kaus kaki Anda saat ini terhadap semua kaus kaki tidak berpasangan dalam array.
  • Dimungkinkan untuk memisahkan kaus kaki ke dalam kelas atau tipe umum (putih / hitam, pergelangan kaki / kru, atletik / pakaian) ketika membangun array Anda, dan "menelusuri" untuk hanya membandingkan suka-untuk-suka.
  • Jika Anda menemukan pasangan yang dapat diterima, kumpulkan kedua kaus kaki dan lepaskan dari array.
  • Jika tidak, masukkan kaus kaki saat ini ke slot terbuka pertama dalam array.
• Ulangi dengan setiap kaus kaki.

Skenario terburuk dari skema ini adalah bahwa setiap pasang kaus kaki cukup berbeda sehingga harus sama persis, dan kaus kaki n / 2 pertama yang Anda pilih semuanya berbeda. Ini adalah skenario O (n ² ) Anda, dan ini sangat tidak mungkin. Jika jumlah jenis yang unik dari kaus kaki t kurang dari jumlah pasangan p = n / 2 , dan kaus kaki pada setiap jenis yang cukup sama (biasanya dalam hal aus terkait) bahwa setiap kaus kaki dari jenis yang dapat dipasangkan dengan lain, maka seperti yang saya simpulkan di atas, jumlah maksimum kaus kaki yang harus Anda bandingkan adalah t , setelah itu yang Anda tarik berikutnya akancocok dengan salah satu kaus kaki tidak berpasangan. Skenario ini jauh lebih mungkin di laci kaus kaki rata-rata daripada kasus terburuk, dan mengurangi kompleksitas kasus terburuk menjadi O (n * t) di mana biasanya t << n .

Pendekatan dunia nyata:

Secepat mungkin, lepaskan kaus kaki dari tumpukan yang tidak disortir pada satu waktu dan letakkan tumpukan di depan Anda. Tumpukan harus diatur agak efisien-ruang, dengan semua kaus kaki menunjuk ke arah yang sama; jumlah tumpukan dibatasi oleh jarak yang dapat Anda jangkau dengan mudah. Pemilihan tumpukan yang digunakan untuk menaruh kaus kaki harus - secepat mungkin - dengan meletakkan kaus kaki di atas tumpukan kaus kaki yang tampaknya seperti; sesekali tipe I (meletakkan kaus kaki di atas tumpukan yang bukan miliknya) atau tipe II (meletakkan kaus kaki di tumpukannya sendiri ketika ada tumpukan kaus kaki sejenis) dapat ditoleransi - pertimbangan terpenting adalah kecepatan .

Setelah semua kaus kaki berada di tumpukan, cepat pergi melalui tumpukan multi-kaus kaki membuat pasangan dan menghapusnya (ini menuju laci). Jika ada kaus kaki yang tidak cocok di tumpukan, tumpukan kembali mereka ke tumpukan terbaik mereka (dalam batasan secepat mungkin) tumpukan. Ketika semua tumpukan multi-kaus kaki telah diproses, cocokkan kaus kaki berpasangan yang tersisa yang tidak dipasangkan karena kesalahan tipe II. Wah, sudah selesai - dan saya punya banyak kaus kaki dan tidak mencucinya sampai sebagian besar kotor. Catatan praktis lain: Saya membalik bagian atas salah satu dari sepasang kaus kaki ke bawah yang lain, mengambil keuntungan dari sifat elastis mereka, sehingga mereka tetap bersama saat diangkut ke laci dan saat di laci.

Dari pertanyaan Anda jelas Anda tidak memiliki banyak pengalaman aktual dengan cucian :). Anda memerlukan algoritme yang berfungsi baik dengan sejumlah kecil kaus kaki yang tidak dapat dipasangkan.

Jawabannya sampai sekarang tidak memanfaatkan kemampuan pengenalan pola manusia kita. Gim Set memberikan petunjuk bagaimana melakukan ini dengan baik: letakkan semua kaus kaki di ruang dua dimensi sehingga Anda berdua bisa mengenalinya dengan baik dan dengan mudah meraihnya dengan tangan Anda. Ini membatasi Anda ke area sekitar 120 * 80 cm atau lebih. Dari sana pilih pasangan yang Anda kenal dan hapus. Letakkan kaus kaki ekstra di ruang kosong dan ulangi. Jika Anda mencuci untuk orang-orang dengan kaus kaki mudah dikenali (anak-anak kecil datang ke pikiran), Anda dapat melakukan semacam radix dengan memilih kaus kaki itu terlebih dahulu. Algoritma ini hanya berfungsi dengan baik ketika jumlah kaus kaki tunggal rendah

Ambil kaus kaki pertama dan letakkan di atas meja. Sekarang pilih kaus kaki lain; jika cocok dengan yang pertama, letakkan di atas yang pertama. Jika tidak, letakkan di atas meja agak jauh dari yang pertama. Pilih kaus kaki ketiga; jika cocok dengan salah satu dari dua sebelumnya, letakkan di atas mereka atau letakkan agak jauh dari yang ketiga. Ulangi sampai Anda mengambil semua kaus kaki.

Untuk mengatakan betapa efisiennya memasangkan kaus kaki dari tumpukan, kita harus mendefinisikan mesin terlebih dahulu, karena pemasangan tidak dilakukan baik oleh turing maupun oleh mesin akses acak, yang biasanya digunakan sebagai dasar untuk suatu analisis algoritmik.

Mesin

Mesin adalah abstraksi dari elemen dunia nyata yang disebut manusia. Ia dapat membaca dari lingkungan melalui sepasang mata. Dan model mesin kami mampu memanipulasi lingkungan dengan menggunakan 2 lengan. Operasi logis dan aritmatika dihitung menggunakan otak kita (semoga ;-)).

Kita juga harus mempertimbangkan runtime intrinsik dari operasi atom yang dapat dilakukan dengan instrumen ini. Karena kendala fisik, operasi yang dilakukan dengan lengan atau mata memiliki kompleksitas waktu yang tidak konstan. Ini karena kita tidak bisa menggerakkan tumpukan besar kaus kaki tanpa ujung dengan tangan juga tidak bisa melihat kaus kaki atas pada tumpukan besar kaus kaki yang tak berujung.

Namun fisika mekanik memberi kita beberapa barang juga. Kami tidak terbatas untuk bergerak paling banyak satu kaus kaki dengan lengan. Kita bisa memindahkan pasangan mereka sekaligus.

Jadi tergantung pada analisis sebelumnya, operasi berikut harus digunakan dalam urutan menurun:

• operasi logis dan aritmatika
• membaca lingkungan
• modifikasi lingkungan

Kita juga dapat memanfaatkan fakta bahwa orang hanya memiliki kaus kaki yang sangat terbatas. Jadi modifikasi lingkungan dapat melibatkan semua kaus kaki di tumpukan.

Algoritma

Jadi, inilah saran saya:

1. Sebarkan semua kaus kaki di tumpukan di atas lantai.
2. Temukan pasangan dengan melihat kaus kaki di lantai.
3. Ulangi dari 2 hingga tidak ada pasangan yang bisa dibuat.
4. Ulangi dari 1 hingga tidak ada kaus kaki di lantai.

Operasi 4 diperlukan, karena ketika menyebarkan kaus kaki di atas lantai, beberapa kaus kaki mungkin menyembunyikan yang lain. Berikut adalah analisis algoritme:

Analisisnya

Algoritma berakhir dengan probabilitas tinggi. Ini disebabkan oleh fakta bahwa seseorang tidak dapat menemukan sepasang kaus kaki pada langkah nomor 2.

Untuk analisis runtime berikut dari memasangkan npasangan kaus kaki, kami menduga bahwa setidaknya setengah dari 2nkaus kaki tidak disembunyikan setelah langkah 1. Jadi dalam kasus rata-rata kita dapat menemukan n/2pasangan. Ini berarti bahwa loop adalah langkah 4 dijalankan O(log n)kali. Langkah 2 dilakukan O(n^2)kali. Jadi kita dapat menyimpulkan:

• Algoritme melibatkan O(ln n + n)modifikasi lingkungan (langkah 1 O(ln n)ditambah mengambil setiap pasang kaus kaki dari lantai)
• Algoritma ini melibatkan O(n^2)pembacaan lingkungan dari langkah 2
• Algoritma ini melibatkan O(n^2)operasi logis dan aritmatika untuk membandingkan kaus kaki dengan yang lain pada langkah 2

Jadi kami memiliki kompleksitas runtime total di O(r*n^2 + w*(ln n + n))mana rdan wmerupakan faktor untuk lingkungan baca dan operasi tulis lingkungan masing-masing untuk jumlah kaus kaki yang wajar. Biaya operasi logis dan aritmetika dihilangkan, karena kami mengira bahwa dibutuhkan operasi logika dan aritmatika dalam jumlah yang konstan untuk memutuskan apakah 2 kaus kaki milik pasangan yang sama. Ini mungkin tidak layak di setiap skenario.

List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

Saya keluar dengan solusi lain yang tidak menjanjikan operasi yang lebih sedikit, tidak sedikit konsumsi waktu, tetapi harus dicoba untuk melihat apakah itu bisa menjadi heuristik yang cukup baik untuk memberikan konsumsi waktu yang lebih sedikit dalam serangkaian besar kaus kaki.

Prasyarat: Tidak ada jaminan bahwa ada kaus kaki yang sama. Jika mereka memiliki warna yang sama, itu tidak berarti mereka memiliki ukuran atau pola yang sama. Kaus kaki secara acak dikocok. Mungkin ada jumlah kaus kaki yang ganjil (ada yang hilang, kami tidak tahu berapa banyak). Bersiaplah untuk mengingat variabel "indeks" dan atur ke 0.

Hasilnya akan memiliki satu atau dua tumpukan: 1. "cocok" dan 2. "hilang"

Heuristis:

1. Temukan kaus kaki paling khas.
2. Temukan kecocokannya.
3. Jika tidak ada yang cocok, letakkan di tumpukan "hilang".
4. Ulangi dari 1. sampai tidak ada lagi kaus kaki yang paling khas.
5. Jika kurang dari 6 kaus kaki, lanjutkan ke 11.
6. Pasangkan secara membabi buta semua kaus kaki dengan tetangganya (jangan mengepaknya)
7. Temukan semua pasangan yang cocok, kemas dan pindahkan pasangan yang dikemas ke tumpukan "cocok"; Jika tidak ada kecocokan baru - tambahkan "indeks" dengan 1
8. Jika "indeks" lebih besar dari 2 (ini bisa menjadi nilai tergantung pada nomor kaus kaki karena dengan jumlah kaus kaki yang lebih besar ada lebih sedikit kesempatan untuk memasangkan mereka secara membabi buta) pergi ke 11
9. Kocok sisanya
10. Pergi ke 1
11. Lupakan "indeks"
12. Pilih kaus kaki
13. Temukan pasangannya
14. Jika tidak ada pasangan untuk kaus kaki, pindahkan ke tumpukan "hilang"
15. Jika kecocokan ditemukan memasangkannya, kemas pasangan dan pindahkan ke tumpukan "cocok"
16. Jika masih ada lebih dari satu kaus kaki pergi ke 12
17. Jika hanya ada satu yang tersisa, pergi ke 14
18. Senyum puas :)

Juga, ada bisa ditambahkan memeriksa kaus kaki yang rusak juga, seolah-olah melepasnya. Itu bisa dimasukkan antara 2 dan 3, dan antara 13 dan 14.

Saya menantikan untuk mendengar pengalaman atau koreksi.

Ketika saya mengurutkan kaus kaki, saya melakukan perkiraan jenis radix , menjatuhkan kaus kaki di dekat kaus kaki lain dengan jenis warna / pola yang sama. Kecuali dalam kasus ketika saya dapat melihat pasangan persis di / dekat lokasi saya akan menjatuhkan kaus kaki saya mengekstrak pasangan pada saat itu.

Hampir semua algoritma lain (termasuk jawaban skor teratas oleh usr ) mengurutkan, lalu hapus pasangan. Saya menemukan bahwa, sebagai manusia, lebih baik untuk meminimalkan jumlah kaus kaki yang dipertimbangkan pada satu waktu.

Saya melakukan ini dengan:

1. Memilih kaus kaki yang khas (apa pun yang menarik perhatian saya di tumpukan).
2. Mulai semacam radix dari lokasi konseptual itu dengan menarik kaus kaki dari tumpukan berdasarkan kesamaan dengan yang itu.
3. Tempatkan kaus kaki baru di dekat tumpukan saat ini, dengan jarak berdasarkan betapa berbedanya itu. Jika Anda menemukan diri Anda meletakkan kaus kaki di atas kaus kaki lain karena identik, bentuk pasangan itu di sana, dan lepaskan kaus kaki itu. Ini berarti bahwa perbandingan di masa depan membutuhkan sedikit usaha untuk menemukan tempat yang benar.

Ini mengambil keuntungan dari kemampuan manusia untuk mencocokkan fuzzy dalam waktu O (1), yang agak setara dengan pembentukan peta hash pada perangkat komputasi.

Dengan menarik kaus kaki khusus terlebih dahulu, Anda menyisakan ruang untuk "memperbesar" fitur-fitur yang kurang khas.

Setelah menghilangkan fluro yang berwarna, kaus kaki dengan garis-garis, dan tiga pasang kaus kaki panjang, Anda mungkin berakhir dengan sebagian besar kaus kaki putih yang secara kasar diurutkan berdasarkan seberapa usang mereka.

Pada titik tertentu, perbedaan antara kaus kaki cukup kecil sehingga orang lain tidak akan melihat perbedaannya, dan upaya pencocokan lebih lanjut tidak diperlukan.

Setiap kali Anda mengambil kaus kaki, letakkan di satu tempat. Kemudian kaus kaki berikutnya yang Anda ambil, jika tidak cocok dengan kaus kaki pertama, letakkan di sebelah yang pertama. Jika ya, ada sepasang. Dengan cara ini, tidak terlalu penting berapa banyak kombinasi yang ada, dan hanya ada dua kemungkinan untuk setiap kaus kaki yang Anda ambil - apakah itu memiliki kecocokan yang sudah ada dalam susunan kaus kaki Anda, atau tidak, yang berarti Anda tambahkan ke tempat dalam array.

Ini juga berarti bahwa Anda hampir pasti tidak akan pernah memiliki semua kaus kaki di dalam array, karena kaus kaki akan dilepas begitu cocok.

Pertimbangkan tabel hash ukuran 'N'.

Jika kita mengasumsikan distribusi normal, maka jumlah perkiraan 'penyisipan' untuk setidaknya satu kaus kaki dipetakan ke satu ember adalah NlogN (yaitu, semua ember penuh)

Saya telah mendapatkan ini sebagai bagian dari teka-teki lain, tetapi saya akan senang terbukti salah. Inilah artikel blog saya yang sama

Biarkan 'N' sesuai dengan perkiraan batas atas pada jumlah warna / pola kaus kaki unik yang Anda miliki.

Setelah Anda mengalami tabrakan (alias: kecocokan) cukup lepaskan kaus kaki itu. Ulangi percobaan yang sama dengan kumpulan kaus kaki NlogN berikutnya. Keindahannya adalah Anda bisa membuat perbandingan paralel NlogN (resolusi tabrakan) karena cara kerja pikiran manusia. :-)

Socks, apakah yang asli atau beberapa struktur data analog, akan disediakan berpasangan.

Jawaban yang paling sederhana adalah sebelum memungkinkan pasangan untuk dipisahkan, struktur data tunggal untuk pasangan harus diinisialisasi yang berisi pointer ke kaus kaki kiri dan kanan, sehingga memungkinkan kaus kaki untuk dirujuk secara langsung atau melalui pasangan mereka. Kaus kaki juga dapat diperpanjang untuk berisi pointer ke mitranya.

Ini memecahkan masalah pemasangan pasangan dengan menghapusnya dengan lapisan abstraksi.

Menerapkan ide yang sama untuk masalah praktis kaus kaki berpasangan, jawaban yang jelas adalah: jangan biarkan kaus kaki Anda tidak pernah berpasangan. Kaus kaki disediakan sebagai pasangan, dimasukkan ke dalam laci sebagai pasangan (mungkin dengan menyatukannya), dipakai sebagai pasangan. Tetapi titik di mana tidak memungkinkan untuk berpasangan adalah di mesin cuci, jadi semua yang diperlukan adalah mekanisme fisik yang memungkinkan kaus kaki untuk tetap bersama dan dicuci secara efisien.

Ada dua kemungkinan fisik:

Untuk objek 'berpasangan' yang membuat pointer ke setiap kaus kaki kita bisa memiliki tas kain yang kita gunakan untuk menjaga kaus kaki bersama. Ini seperti overhead besar.

Tetapi untuk setiap kaus kaki tetap mengacu pada yang lain, ada solusi yang rapi: popper (atau 'tombol jepret' jika Anda orang Amerika), seperti ini:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Kemudian semua yang Anda lakukan adalah kencangkan kaus kaki Anda tepat setelah Anda melepasnya dan menaruhnya di keranjang cuci Anda, dan sekali lagi Anda telah menghilangkan masalah perlu memasangkan kaus kaki Anda dengan abstraksi fisik dari konsep 'pasangan'.

Jika operasi "pindah" cukup mahal, dan operasi "bandingkan" itu murah, dan Anda tetap harus memindahkan seluruh rangkaian, ke dalam buffer di mana pencarian jauh lebih cepat daripada di penyimpanan asli ... cukup mengintegrasikan penyortiran ke dalam kewajiban. pindah.

Saya menemukan mengintegrasikan proses pengurutan menjadi menggantung menjadi mudah. Saya perlu mengambil masing-masing kaus kaki, dan menggantungnya (bergerak) dan saya tidak perlu mengeluarkan apa pun untuk menggantungnya di tempat tertentu di senar. Sekarang tidak memaksa pencarian seluruh buffer (string) saya memilih untuk menempatkan kaus kaki dengan warna / bayangan. Lebih gelap ke kiri, lebih terang ke kanan, lebih berwarna di bagian depan dll. Sekarang sebelum saya menggantung setiap kaus kaki, saya melihat di "sekitar kanan" jika sudah ada yang cocok - ini membatasi "memindai" ke 2-3 kaus kaki lainnya - dan jika itu adalah , Saya menggantung yang lain tepat di sebelahnya. Lalu aku menggulungnya menjadi berpasangan saat melepaskan dari string, saat kering.

Sekarang ini mungkin tidak tampak jauh berbeda dari "membentuk tumpukan dengan warna" yang disarankan oleh jawaban atas tetapi pertama-tama, dengan tidak memilih tumpukan terpisah tetapi rentang, saya tidak punya masalah mengklasifikasikan apakah "ungu" pergi ke tumpukan "merah" atau "biru"; hanya berjalan di antara. Dan kemudian dengan mengintegrasikan dua operasi (menggantung kering dan mengurutkan) overhead penyortiran sambil menggantung seperti 10% dari apa yang akan menyortir terpisah.

Saya sudah selesai memasangkan kaus kaki saya sekarang, dan saya menemukan bahwa cara terbaik untuk melakukannya adalah sebagai berikut:

• Pilih salah satu kaus kaki dan simpan (buat 'ember' untuk pasangan itu)
• Jika yang berikutnya adalah pasangan dari yang sebelumnya, maka taruh ke ember yang ada, jika tidak buat yang baru.

Dalam kasus terburuk itu berarti Anda akan memiliki n / 2 ember berbeda, dan Anda akan memiliki n-2 penentuan tentang ember mana yang berisi sepasang kaus kaki saat ini. Jelas, algoritma ini bekerja dengan baik jika Anda hanya memiliki beberapa pasangan; Saya melakukannya dengan 12 pasang.

Ini tidak begitu ilmiah, tetapi bekerja dengan baik :)

Solusi saya tidak persis sesuai dengan kebutuhan Anda, karena itu membutuhkan secara formal O(n) ruang "ekstra". Namun, mengingat kondisi saya itu sangat efisien dalam aplikasi praktis saya. Jadi saya pikir itu harus menarik.

Kombinasikan dengan Tugas Lain

Kondisi khusus dalam kasus saya adalah bahwa saya tidak menggunakan mesin pengering, hanya menggantungkan pakaian saya pada pengering kain biasa. Menggantung kain membutuhkan O(n)operasi (omong-omong, saya selalu mempertimbangkan kemasan bin masalah sini) dan masalah pada dasarnya membutuhkan ruang "ekstra" linear. Ketika saya mengambil kaus kaki baru dari ember saya mencoba menggantungnya di sebelah pasangannya jika pasangan sudah digantung. Jika itu kaus kaki dari pasangan baru saya meninggalkan beberapa ruang di sebelahnya.

Mesin Oracle Lebih Baik ;-)

Jelas membutuhkan kerja ekstra untuk memeriksa apakah ada kaus kaki yang cocok sudah tergantung di suatu tempat dan itu akan memberikan solusi O(n^2)dengan koefisien sekitar 1/2untuk komputer. Tetapi dalam kasus ini "faktor manusia" sebenarnya merupakan keuntungan - saya biasanya dapat dengan sangat cepat (hampir O(1)) mengidentifikasi kaus kaki yang cocok jika sudah digantung (mungkin beberapa caching di otak yang tidak terlihat terlibat) - menganggapnya sebagai semacam terbatas "oracle" seperti pada Oracle Machine ;-) Kami, manusia memiliki kelebihan ini dibandingkan mesin digital dalam beberapa kasus ;-)

Sudah Hampir O(n) !

Dengan demikian menghubungkan masalah kaus kaki berpasangan dengan masalah kain gantung, saya mendapatkan O(n)"ruang ekstra" secara gratis, dan memiliki solusi yang O(n)tepat waktu, hanya membutuhkan sedikit lebih banyak pekerjaan daripada kain gantung sederhana dan memungkinkan untuk segera mengakses pasangan lengkap kaus kaki. kaus kaki bahkan di Senin pagi yang sangat buruk ... ;-)

Saya harap saya dapat berkontribusi sesuatu yang baru untuk masalah ini. Saya perhatikan bahwa semua jawaban mengabaikan fakta bahwa ada dua poin di mana Anda dapat melakukan preprocessing , tanpa memperlambat kinerja cucian Anda secara keseluruhan.

Juga, kita tidak perlu mengasumsikan sejumlah besar kaus kaki, bahkan untuk keluarga besar. Kaus kaki dikeluarkan dari laci dan dipakai, dan kemudian dilempar ke suatu tempat (mungkin tempat sampah) tempat mereka tinggal sebelum dicuci. Sementara saya tidak akan menyebut kata bin LIFO-Stack, saya akan mengatakan aman untuk menganggap itu

1. orang-orang melemparkan kedua kaus kaki mereka secara kasar di area yang sama dari tempat sampah,
2. tempat sampah tidak diacak kapan saja, dan karenanya
3. setiap himpunan bagian yang diambil dari bagian atas nampan ini umumnya berisi kedua kaus kaki sepasang.

Karena semua mesin cuci yang saya tahu memiliki ukuran terbatas (terlepas dari berapa banyak kaus kaki yang harus Anda cuci), dan pengacakan yang sebenarnya terjadi di mesin cuci, tidak peduli berapa banyak kaus kaki yang kita miliki, kami selalu memiliki subset kecil yang mengandung hampir tidak ada lajang.

Dua tahap preprocessing kami adalah "meletakkan kaus kaki di tali jemuran" dan "Mengambil kaus kaki dari tali jemuran", yang harus kami lakukan, untuk mendapatkan kaus kaki yang tidak hanya bersih tetapi juga kering. Seperti halnya mesin cuci, jemuran terbatas, dan saya berasumsi bahwa kita memiliki seluruh bagian dari garis tempat kita menaruh kaus kaki kita.

Berikut algoritma untuk put_socks_on_line ():

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

Jangan buang waktu Anda untuk memindahkan kaus kaki atau mencari pasangan yang cocok, ini semua harus dilakukan di O (n), yang juga akan kita perlukan untuk menempatkannya di telepon tanpa disortir. Kaus kaki belum dipasangkan, kami hanya memiliki beberapa cluster kesamaan di telepon. Sangat membantu bahwa kita memiliki satu set kaus kaki terbatas di sini, karena ini membantu kita untuk membuat kelompok "baik" (misalnya, jika hanya ada kaus kaki hitam di set kaus kaki, pengelompokan dengan warna tidak akan menjadi cara untuk pergi)

Berikut algoritma untuk take_socks_from_line ():

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

Saya harus menunjukkan bahwa untuk meningkatkan kecepatan langkah-langkah yang tersisa, adalah bijaksana untuk tidak secara acak memilih kaus kaki berikutnya, tetapi secara berurutan mengambil kaus kaki setelah kaus kaki dari masing-masing kelompok. Kedua langkah preprocessing tidak memakan waktu lebih dari sekadar meletakkan kaus kaki di garis atau di keranjang, yang harus kita lakukan tidak peduli apa, jadi ini harus sangat meningkatkan kinerja binatu.

Setelah ini, mudah untuk melakukan algoritma partisi hash. Biasanya, sekitar 75% dari kaus kaki sudah dipasangkan, meninggalkan saya dengan subset kaus kaki yang sangat kecil, dan subset ini sudah (agak) terkelompok (saya tidak memasukkan banyak entropi ke keranjang saya setelah langkah preprocessing). Hal lain adalah bahwa cluster yang tersisa cenderung cukup kecil untuk ditangani sekaligus, sehingga dimungkinkan untuk mengeluarkan seluruh cluster dari keranjang.

Berikut algoritma untuk sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

Setelah itu, hanya ada beberapa kaus kaki yang tersisa. Di sinilah saya memperkenalkan kaus kaki yang sebelumnya tidak berpasangan ke dalam sistem dan memproses kaus kaki yang tersisa tanpa algoritma khusus - kaus kaki yang tersisa sangat sedikit dan dapat diproses secara visual dengan sangat cepat.

Untuk semua kaus kaki yang tersisa, saya berasumsi bahwa rekan-rekan mereka masih belum dicuci dan menyimpannya untuk iterasi berikutnya. Jika Anda mendaftarkan pertumbuhan kaus kaki tidak berpasangan dari waktu ke waktu ("kebocoran kaus kaki"), Anda harus memeriksa nampan Anda - mungkin akan diacak (apakah Anda memiliki kucing yang tidur di sana?)

Saya tahu bahwa algoritma ini mengambil banyak asumsi: tempat sampah yang bertindak sebagai semacam tumpukan LIFO, mesin cuci normal, terbatas, dan tali jemuran normal terbatas - tetapi ini masih berfungsi dengan jumlah kaus kaki yang sangat besar.

Tentang paralelisme: Selama Anda melemparkan kedua kaus kaki ke tempat sampah yang sama, Anda dapat dengan mudah memparalelkan semua langkah itu.

Saya telah mengambil langkah-langkah sederhana untuk mengurangi upaya saya menjadi proses yang memakan waktu O (1).

Dengan mengurangi input saya ke salah satu dari dua jenis kaus kaki (kaus kaki putih untuk rekreasi, kaus kaki hitam untuk pekerjaan), saya hanya perlu menentukan mana dari dua kaus kaki yang saya miliki. (Secara teknis, karena mereka tidak pernah dicuci bersama, saya telah mengurangi proses menjadi O (0) waktu.)

Beberapa upaya dimuka diperlukan untuk menemukan kaus kaki yang diinginkan, dan untuk membeli dalam jumlah yang cukup untuk menghilangkan kebutuhan kaus kaki yang ada. Karena saya telah melakukan ini sebelum saya membutuhkan kaus kaki hitam, usaha saya minimal, tetapi jarak tempuh dapat bervariasi.

Upaya dimuka seperti itu telah dilihat berkali-kali dalam kode yang sangat populer dan efektif. Contohnya termasuk # DEFINE'ing pi ke beberapa desimal (contoh lain ada, tapi itulah yang terlintas dalam pikiran saat ini).

Buat tabel hash yang akan digunakan untuk kaus kaki yang tidak cocok, menggunakan pola sebagai hash. Ulangi kaus kaki satu per satu. Jika kaus kaki memiliki pola yang cocok di tabel hash, keluarkan kaus kaki dari tabel dan buat pasangan. Jika kaus kaki tidak memiliki korek api, masukkan ke meja.

Masalah mengurutkan n kaus kaki Anda adalah O (n) . Sebelum Anda melemparkannya ke keranjang cucian , Anda benang yang kiri ke yang kanan. Saat mengeluarkannya, Anda memotong utas dan menempatkan setiap pasangan ke dalam laci Anda - 2 operasi pada n pasangan, jadi O (n).

Sekarang pertanyaan selanjutnya adalah apakah Anda mencuci pakaian sendiri dan istri Anda mencuci pakaiannya sendiri. Itu adalah masalah yang kemungkinan berada dalam domain masalah yang sama sekali berbeda . :)