Saya ingin menulis algoritma “ultimate shuffle” untuk mengurutkan koleksi mp3 saya

Saya mencari saran kode pseudocode untuk menyortir file mp3 saya dengan cara yang menghindari pengulangan judul dan artis . Saya mendengarkan crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald dll. Menyanyikan lagu-lagu standar lama. Setiap artis merekam banyak lagu yang sama - Terbang Me To The Moon, Cara Anda Melihat Malam Ini, Stardust dll. Tujuan saya adalah mengatur lagu (atau memesan daftar putar) dengan ruang maksimum antara artis dan judul lagu. Jadi jika saya memiliki 2000 lagu dan 20 lagu oleh Ella saya ingin mendengarnya hanya sekali dalam setiap 100 lagu. Jika 10 artis menyanyikan Fly Me To The Moon saya ingin mendengarnya sekali dalam setiap 200 lagu. Tentu saja saya ingin menggabungkan kedua persyaratan ini untuk membuat "shuffle pamungkas" saya.

Saya tahu ini adalah pertanyaan terbuka yang cukup luas. Saya belum mulai memprogramnya, jadi saya hanya mencari saran untuk pendekatan yang baik. Saya sebenarnya memiliki beberapa persyaratan lain mengenai penempatan atribut lagu lainnya secara merata tetapi saya tidak akan membahasnya di sini.

Sebagai titik awal saya memodifikasi kode yang saya temukan di sini untuk memanipulasi file mp3 dan membaca tag ID3.

Saya menulis aplikasi kecil yang memenuhi kebutuhan saya menggunakan jawaban parsifal di bawah ini. Saya juga menulis pertanyaan tindak lanjut di sini . Terima kasih atas semua tanggapan yang luar biasa!

Apakah Anda ingin menjalankan program Anda sekali dan menghasilkan daftar putar, atau memilih lagu berikutnya secara langsung?

Jika yang terakhir, maka jawabannya sederhana:

• Buat larik yang berisi semua lagu Anda, dengan artis dan judul
• Buat daftar (daftar tertaut lebih disukai) untuk menampung judul lagu yang baru diputar. Daftar ini dimulai dengan kosong, dan setiap kali Anda memainkan lagu Anda menambahkannya ke daftar. Ketika daftar mencapai ukuran "no song repeat" yang Anda inginkan, lepaskan entri terlama (pertama).
• Ditto untuk daftar artis.

Memilih lagu kemudian menjadi urutan langkah-langkah berikut:

1. Pilih lagu secara acak dari larik "semua lagu". Ini hanya angka acak antara 0 dan ukuran array.
2. Lihat apakah lagu itu sudah ada dalam daftar lagu yang diputar. Jika ya, kembali ke langkah # 1.
3. Lihat apakah artis sudah ada dalam daftar artis yang diputar. Jika ya, kembali ke langkah # 1.
4. Tambahkan artis lagu / judul ke daftar yang sesuai, menjatuhkan entri lama jika diperlukan.
5. Mainkan lagunya.

Ada beberapa masalah yang mungkin terjadi, tetapi itu hanya masalah jika Anda melakukan ini sebagai pekerjaan rumah dan bukan proyek nyata.

• Seperti @Dukeling katakan dalam komentar, jika koleksi Anda secara dramatis tidak seimbang dalam mendukung artis tunggal atau judul lagu, Anda dapat masuk ke lingkaran di mana Anda terus-menerus menolak lagu. Dalam praktiknya, ini tidak akan menjadi masalah. Solusinya adalah Anda perlu mengurangi ukuran daftar "sudah terlihat". Dan menambahkan penghitung di langkah # 2 dan # 3 dapat memberi tahu Anda jika ini merupakan masalah (jika Anda melihat 10 kegagalan berturut-turut, angkat peringatan dan / atau kurangi ukuran daftar).
• Jika Anda mencoba membuat daftar putar yang berisi semua lagu yang diputar hanya sekali, Anda harus menghapus lagu dari susunan sumber. Ini juga akan mengubah cara Anda menangani terlalu banyak kegagalan "yang baru diputar" (karena pada akhirnya Anda mungkin hanya memiliki satu artis di larik sumber Anda).
• Jika tag ID3 Anda seperti milik saya, tag itu berisi banyak kesalahan ejaan. Apakah "Duke Ellington" harus berbeda dari "Duke Elingten"? Jika ya, maka coba gunakan pencocokan Levenstein saat memindai daftar "yang baru diputar".

Saya telah melakukan sesuatu seperti ini sebelum menggunakan generator (dalam C #, sebuah loop tak terbatas yang yieldsetiap iterasi loop). Setiap iterasi melihat kumpulan lagunya (atau apa pun) dan mengeluarkan yang telah diputar terlalu baru (atau kriteria negatif apa pun). Kemudian Anda memilih satu dari daftar yang difilter, dan memperbarui status Anda. Saat keadaan Anda melayang (Anda memainkan lagu-lagu non-Sinatra) kriteria rusak dan lagu-lagu Anda yang dikecualikan mulai dimasukkan kembali.

Tentu saja ada kasus sudut untuk ditangani:

• Apa yang terjadi jika Anda membuang semua lagu? (Biasanya hanya memilih satu secara acak, berharap untuk membuat negara tidak stabil)
• Haruskah beberapa kriteria dipilih? (biasanya demikian, mungkin Anda tidak ingin bermain Terbang Me ke Bulan kembali ke belakang, dan lebih suka untuk tidak bermain Sinatra kembali ke belakang, tetapi jika hanya itu yang Anda miliki ...)
• Apa yang terjadi jika koleksi lagu Anda diperbarui di pertengahan pertarungan? (biasanya mudah ditangani, tetapi konkurensi mungkin memiliki masalah tergantung pada penggunaan)

Mengabaikan outlier pertanyaan Anda yang diangkat Telastyn, sepertinya Anda memiliki variasi pada masalah ransel . Untungnya, ini adalah algoritma yang didokumentasikan dengan cukup baik.

Dari Wikipedia

Diberikan satu set item, masing-masing dengan berat dan nilai, tentukan jumlah setiap item untuk dimasukkan dalam koleksi sehingga total berat kurang dari atau sama dengan batas yang diberikan dan nilai total adalah sebesar mungkin.

Ada beberapa variasi yang berpotensi relevan yang tercantum dalam artikel itu bersama dengan daftar tambahan masalah ransel

Salah satu variasi dari masalah ransel adalah masalah ransel multi-tujuan. The koloni semut algoritma disarankan sebagai sarana memecahkan masalah itu. Pendekatan koloni semut mungkin merupakan cara termudah bagi Anda untuk menghindari aspek-aspek sulit NP dari pertanyaan Anda.

Saya juga bisa melihat mempertimbangkan masalah Anda sebagai varian ekstrem dari masalah salesman keliling . Setiap kota yang dikunjungi adalah lagu yang ingin Anda mainkan, tetapi saya tidak yakin bagaimana Anda akan menentukan interval antara artis. Saran ini juga terkait dengan / dapat diselesaikan dengan pendekatan koloni semut.

Saya bekerja dengan asumsi bahwa ini adalah "di sini adalah perpustakaan saya, jalankan program ini dan buat perintah untuk memutar lagu-lagu."

Ini belum diimplementasikan dan saya tidak yakin seberapa baik itu akan mengubah bentuknya. Mungkin karena saya agak terlalu ketat dalam filter, yang akan menghasilkan (saya percaya) dalam urutan yang ditentukan untuk sisanya diberi set lagu awal.

Seseorang memiliki ideal_gaphash. Ini dihitung oleh kepadatan lagu dengan properti yang diberikan (artis, album, judul). Jika seseorang memiliki 2000 lagu dan 20 di antaranya oleh seorang seniman bernama Ella, itu ideal_gap{'artist'}{"ella"}akan menjadi 100.

Memiliki informasi ini, seseorang juga memiliki nilai-nilai ideal_gap maksimal. Mari kita panggil ini max_gap.

Pertimbangkan: memiliki nilai maksimum untuk ideal_gapmencegah lagu yang hanya dinyanyikan oleh dua artis agar lagu lain tidak dimainkan 1000 lagu nanti, dan juga secara drastis meningkatkan nilai max_gap yang menghasilkan banyak iterasi "mundur, tidak ada lagu, kembali tidak aktif, tidak ada lagu ".

Memeriksa lagu max_gap terakhir yang diputar (ini dapat diisi dari tayangan sebelumnya sehingga jika selesai dengan Frank Sinatra menyanyikan Fly Me To the Moon, tayangan berikutnya tidak akan dimulai dengan lagu yang sama secara kebetulan), satu menyaring lagu dari perpustakaan menghasilkan satu set lagu kandidat. Sebuah lagu hanya akan ada di lagu kandidat jika semua celahnya kurang dari ideal_gapuntuk properti tersebut.

Dari kumpulan lagu kandidat, pilih satu secara acak.

Pertimbangkan: menimbang set sehingga lagu-lagu yang atribut dengan gap max lebih tinggi akan lebih mungkin. Dengan cara ini, orang tidak memiliki semua lagu max gap yang lebih besar yang menumpuk di akhir daftar putar.

Pertimbangkan: alih-alih memiliki ketiga properti lebih besar dari kesenjangan ideal, hanya dua dari tiga. Ini mungkin berarti bahwa sesuatu dapat dimainkan lebih cepat dari ideal ideal, tetapi meningkatkan ukuran set lagu kandidat yang berarti "pilih satu secara acak" memiliki opsi lebih banyak.

Jika tidak ada lagu yang memenuhi persyaratan, mundur max_gapdengan 1, dan semua ideal_gaps oleh n/max_gappersen di mana nberapa kali ini telah dibatalkan. Dengan cara ini jika ada max_gap100, dan telah mundur 5 kali dalam iterasi ini, ideal_gap 100 akan disesuaikan untuk sementara menjadi 95, dan ideal_gap 20 akan disesuaikan untuk sementara menjadi 19. Ulangi mundur dari gap sampai ada setidaknya satu lagu kandidat, dan kemudian pilih seperti di atas.

Pertimbangkan: memiliki ukuran kolam minimum. Ini menambah varians, tetapi dapat mengakibatkan lagu diputar lebih cepat dari kesenjangan ideal ketika ada lagu lain yang bisa dimainkan.

Ini adalah pekerjaan optimasi, dan yang cukup rumit jika Anda mencari yang solusi optimal. Untungnya saya percaya itu menjadi salah satu kasus di mana cukup baik akan dilakukan.

Hal pertama yang harus dilakukan adalah menetapkan kriteria kualitas matematika, yaitu formula yang diberi permutasi dari daftar akan menghasilkan angka tunggal yang menggambarkan seberapa baik atau buruk permutasi itu.

Saran rumus sederhana, setiap kriteria yang ingin Anda perhitungkan harus diberi bobot, memberi bobot tinggi pada kriteria penting, dan bobot rendah pada kriteria di mana banyak lagu berbagi properti yang sama, sehingga yang tidak mendominasi :

For each song on the list
    For each other song on the list
        For each criteria
            If the two songs share that criteria
                Add to the quality value: square root( [criteria weight]/[distance between the two songs] )

Semakin rendah nilai yang dihasilkan oleh prosedur ini, semakin baik permutasi daftar.

Membuat permutasi

Sekarang Anda dapat mengambil rumus ini ke math.stackexchange dan minta mereka memberi tahu Anda betapa sulitnya dan mungkin secara praktis mustahil untuk menemukan solusi optimal untuk apa pun kecuali sejumlah lagu yang sepele, atau Anda bisa melempar siklus jam ke sana dan mendapatkan solusi bagus

Ada banyak cara untuk melakukan ini, ini salah satunya:

Start with a random permutation of the list.
Several million times do the following:
    Select two entries at random
    For each of those two entries calculate their contribution to the quality value
    Swap the positions of the two entries
    Calculate the contribution to the quality value of the two entries at their new position
    If the sum of the calculations in the new positions is greater than the sum in the old positions
        Swap back

Ini adalah algoritma yang agak boros, tetapi mudah diimplementasikan dan dapat menangani kriteria sebanyak satu keinginan.

Optimalisasi

Banyak penyesuaian dan pengoptimalan yang berbeda dapat diterapkan, berikut adalah beberapa:

Dalam perhitungan nilai kualitas, jangan repot-repot memeriksa lagu terhadap setiap lagu lain dalam daftar, alih-alih periksa saja terhadap 100 atau lebih lagu terdekat. Untuk nilai-nilai umum, optimasi kecepatan ini praktis tidak berpengaruh pada kualitas hasil.

Untuk nilai langka dari properti yang diberikan, mungkin lebih efisien untuk melacak contoh yang ada dari nilai itu daripada mencari mereka.

Jika Anda merasa bahwa penting bahwa nilai-nilai yang memiliki beberapa contoh berjarak dekat dengan genap, daripada hanya berjauhan mungkin diperlukan untuk meningkatkan bobot untuk nilai-nilai spesifik tersebut, tetapi tidak untuk nilai-nilai lain dari kriteria itu.

Fungsi pseudo-acak yang mengambil semua pasangan yang mungkin dari daftar dalam distribusi yang sama mungkin memiliki efisiensi per pilihan yang sedikit lebih baik daripada pilihan acak yang normal.

Sangat menarik apa pendekatan yang berbeda yang diambil orang. Saya akan melakukan yang berikut:

Berdasarkan semua trek yang dimainkan sejauh ini, beri masing-masing skor. Mainkan trek dengan skor terendah (atau, dalam kasus skor identik, acak yang cocok dengan skor terendah). Ulangi.

Bagian yang sulit, tentu saja, adalah memberikan skor. Untuk setiap trek yang mungkin Anda mainkan berikutnya, Anda harus melewati setiap (atau jumlah terbatas) trek yang sudah Anda mainkan. Jika trek [mungkin berikutnya] dan trek [yang baru diputar] memiliki sesuatu yang sama, Anda menambah skor, tergantung pada seberapa banyak kesamaan mereka, apa kesamaan mereka, dan berapa lama lintasan [yang baru diputar] itu dimainkan. Anda mungkin ingin "sama sekali tidak sama" menjadi 0, sehingga Anda dapat memulai dengan semua trek sebagai 0.

Anda mungkin ingin bereksperimen dengan beberapa playlist kerajinan tangan untuk memulai, untuk mendapatkan matematika yang benar - apakah Anda ingin jumlah kata yang sama, atau kuadrat dari jumlah kata yang sama, atau akar kuadrat dari angka kata-kata yang sama? Jalankan seluruh daftar putar Anda, lihat mana yang melayang ke atas sebagai "paling umum", dan sesuaikan faktor untuk mendapatkan keseimbangan yang tepat. Mungkin Anda ingin menulis per huruf, jadi "Duke Ellington" memiliki skor tinggi bila dibandingkan dengan "Duke Elington", tetapi skor lebih tinggi jika dibandingkan dengan "King Elle Duton" (jika saya tidak kehilangan huruf :) . Anda harus mempertimbangkan dengan cermat bidang mana yang ingin Anda bandingkan, dan jika Anda ingin membandingkan antar bidang. Anda bahkan dapat mempertimbangkan bigrams (pasangan surat; dalam kasus Duke ellington, "Du", "

Perhatikan bahwa, jika Anda memiliki banyak artis tertentu, artis itu mungkin akan turun dalam prioritas - Anda mungkin mendengar trek oleh artis unik 5 kali, sebelum Anda mendengar semua 10 lagu Duke Ellington Anda. Ini mungkin atau mungkin bukan yang Anda inginkan. Anda dapat menghindari ini dengan membuat kamus dari semua yang Anda harus membandingkan, dan seberapa sering mereka terjadi, jadi jika Anda memiliki banyak lagu Duke Ellington, dua lagu yang oleh Duke Ellington "kurang mirip" daripada dua oleh Billy Joe Shaver .

Bahkan mungkin layak pra-menghitung tabel dengan setiap kombinasi dari dua pasang lagu. Juga, ketika mempertimbangkan lagu mana yang akan diputar berikutnya, Anda hanya perlu mengingat lagu terbaik sejauh ini; jika lagu berikutnya yang dipertimbangkan memiliki skor lebih buruk daripada lagu terbaik sejauh ini, Anda dapat melompat ke lagu berikutnya.