Kata Siklik
Pernyataan masalah
Kita dapat menganggap kata siklik sebagai kata yang ditulis dalam lingkaran. Untuk mewakili kata siklik, kami memilih posisi awal yang sewenang-wenang dan membaca karakter dalam urutan searah jarum jam. Jadi, "gambar" dan "turepic" adalah representasi untuk kata siklik yang sama.
Anda diberi kata String [], yang setiap elemennya merupakan representasi kata siklik. Kembalikan jumlah kata siklik yang berbeda yang diwakili.
Kemenangan tercepat (Big O, di mana n = jumlah karakter dalam sebuah string)
word-puzzle
counting
fastest-algorithm
telur dadu
sumber
sumber
Jawaban:
Python
Inilah solusi saya. Saya pikir itu mungkin masih O (n 2 ), tapi saya pikir kasus rata-rata jauh lebih baik dari itu.
Pada dasarnya ini bekerja dengan menormalkan setiap string sehingga setiap rotasi akan memiliki bentuk yang sama. Sebagai contoh:
Normalisasi dilakukan dengan mencari karakter minimum (dengan kode char), dan memutar string sehingga karakter berada di posisi terakhir. Jika karakter itu muncul lebih dari satu kali, maka karakter setelah setiap kejadian digunakan. Ini memberikan setiap kata siklik representasi kanonik, yang dapat digunakan sebagai kunci dalam peta.
Normalisasi adalah n 2 dalam kasus terburuk (di mana setiap karakter dalam string adalah sama, misalnya
aaaaaa
), tetapi sebagian besar waktu hanya akan ada beberapa kejadian, dan waktu berjalan akan lebih dekatn
.Di laptop saya (dual core Intel Atom @ 1.66GHz dan ram 1GB), menjalankan ini
/usr/share/dict/words
(234.937 kata dengan panjang rata-rata 9,5 karakter) membutuhkan waktu sekitar 7,6 detik.sumber
Python (3) lagi
Metode yang saya gunakan adalah untuk menghitung hash bergulir dari setiap kata dimulai pada setiap karakter dalam string; karena ini adalah hash yang bergulir, dibutuhkan O (n) (di mana n adalah panjang kata) waktu untuk menghitung semua hash n. String diperlakukan sebagai nomor basis-1114112, yang memastikan hash unik. (Ini mirip dengan solusi Haskell, tetapi lebih efisien karena hanya melewati string dua kali.)
Kemudian, untuk setiap kata input, algoritme memeriksa hash terendah untuk melihat apakah hash sudah ada dalam kumpulan hash yang terlihat (himpunan Python, sehingga pencariannya adalah O (1) dalam ukuran himpunan); jika ya, maka kata atau salah satu rotasinya sudah terlihat. Kalau tidak, ia menambahkan hash ke set.
Argumen baris perintah haruslah nama file yang berisi satu kata per baris (seperti
/usr/share/dict/words
).sumber
Haskell
Tidak yakin dengan efisiensi ini, kemungkinan besar agak buruk. Idenya adalah untuk pertama-tama membuat semua kemungkinan rotasi dari semua kata, menghitung nilai-nilai yang secara unik mewakili string dan memilih minimum. Dengan begitu kita mendapatkan nomor yang unik untuk grup siklik.
Kami dapat mengelompokkan berdasarkan nomor ini dan memeriksa jumlah grup ini.
Jika n adalah jumlah kata dalam daftar dan m adalah panjang kata maka hitung 'nomor kelompok siklik' untuk semua kata tersebut
O(n*m)
, pengurutanO(n log n)
dan pengelompokanO(n)
.sumber
Mathematica
Memutuskan untuk memulai lagi, sekarang saya mengerti aturan permainan (saya pikir).
Kamus 10.000 kata dengan "kata-kata" unik yang disusun secara acak (hanya huruf kecil) dengan panjang 3. Dengan cara yang sama, kamus lain dibuat yang terdiri dari string dengan panjang 4, 5, 6, 7, dan 8.
g
mengambil versi kamus saat ini untuk memeriksa. Kata teratas digabungkan dengan varian siklik (jika ada). Kata dan kecocokannya ditambahkan ke daftar outputout
,, dari kata-kata yang diproses. Kata-kata keluaran dihapus dari kamus.f
berjalan melalui semua kata kamus.Contoh 1 : kata-kata aktual
Contoh 2 : Kata-kata tiruan. Kamus string panjang 3. Pertama, waktu. Kemudian jumlah kata siklus.
Pengaturan waktu sebagai fungsi dari panjang kata . 10000 kata dalam setiap kamus.
Saya tidak terlalu tahu bagaimana menafsirkan temuan dalam hal O. Secara sederhana, waktunya kira-kira dua kali lipat dari kamus tiga karakter ke kamus empat karakter. Penentuan waktunya meningkat hampir secara diabaikan dari 4 hingga 8 karakter.
sumber
Ini dapat dilakukan dalam O (n) menghindari waktu kuadratik. Idenya adalah untuk membangun lingkaran penuh melintasi string dasar dua kali. Jadi kami membangun "amazingamazin" sebagai string lingkaran penuh untuk memeriksa semua string siklik yang sesuai dengan "menakjubkan".
Di bawah ini adalah solusi Java:
sumber
Saya tidak tahu apakah ini sangat efisien, tetapi ini adalah celah pertama saya.
sumber
Perl
tidak yakin saya mengerti masalahnya, tapi ini cocok dengan contoh @dude diposting di komentar setidaknya. tolong perbaiki analisis saya yang pasti salah.
untuk setiap kata W dalam kata-kata N yang diberikan dari daftar string, Anda harus menelusuri semua karakter W dalam kasus terburuk. saya harus menganggap operasi hash dilakukan dalam waktu yang konstan.
sumber