Cari tahu giliran siapa yang membeli croissant

Sebuah tim telah memutuskan bahwa setiap pagi seseorang harus membawa croissant untuk semua orang. Seharusnya tidak ada orang yang sama setiap saat, jadi harus ada sistem untuk menentukan giliran siapa selanjutnya. Tujuan dari pertanyaan ini adalah untuk menentukan algoritma untuk memutuskan giliran siapa yang akan membawa croissant besok.

Kendala, asumsi dan tujuan:

• Giliran siapa itu untuk membawa croissant akan ditentukan sore sebelumnya.
• Pada hari tertentu, beberapa orang tidak hadir. Algoritma harus memilih seseorang yang akan hadir pada hari itu. Asumsikan bahwa semua absen diketahui sehari sebelumnya, sehingga pembeli croissant dapat ditentukan pada sore sebelumnya.
• Secara keseluruhan, kebanyakan orang hadir hampir setiap hari.
• Demi keadilan, setiap orang harus membeli croissant sebanyak yang lainnya. (Pada dasarnya, anggap setiap anggota tim memiliki jumlah uang yang sama untuk dihabiskan untuk croissant.)
• Akan menyenangkan untuk memiliki beberapa elemen keacakan, atau setidaknya dirasakan keacakan, untuk mengurangi kebosanan daftar. Ini bukan kendala yang sulit: ini lebih merupakan penilaian estetika. Namun, orang yang sama tidak boleh dipetik dua kali berturut-turut.
• Orang yang membawa croissant harus tahu sebelumnya. Jadi, jika orang P membawa croissant pada hari D, maka fakta ini harus ditentukan pada beberapa hari sebelumnya di mana orang P hadir. Misalnya, jika pembawa croissant selalu ditentukan sehari sebelumnya, maka itu harus menjadi salah satu dari orang-orang yang hadir sehari sebelumnya.
• Jumlah anggota tim cukup kecil sehingga sumber daya penyimpanan dan komputasi secara efektif tidak terbatas. Misalnya algoritma dapat mengandalkan sejarah lengkap tentang siapa yang membawa croissant ketika di masa lalu. Penghitungan beberapa menit pada PC cepat setiap hari akan baik-baik saja.

Ini adalah model masalah dunia nyata, jadi Anda bebas untuk menantang atau memperbaiki asumsi jika Anda berpikir bahwa mereka membuat model skenario yang lebih baik.

Asal: Cari tahu siapa yang akan membeli croissant oleh Florian Margaine . Reformulasi saya di sini memiliki persyaratan yang sedikit berbeda.

Ada dua kategori solusi untuk masalah semacam ini yang saya ketahui: lotere bias dan disaring / dihasilkan secara acak .

Pertama, mari kita keluarkan dengan solusi mudah tapi salah yang tidak membuat negara. Solusi gaya lotre apa pun yang tidak mempertahankan keadaan akan memiliki jumlah kemenangan dalam distribusi binomial, yang gagal kriteria "sebanyak" kali. Anda dapat memilih urutan acak yang mengambil semua orang sama (hanya berkeliling daftar melakukan itu; permutasi memberikan keacakan), tetapi begitu orang mulai pergi liburan urutan Anda sekarang memiliki lubang. Kecuali Anda melacak, Anda akan menemukan diri Anda dengan distribusi binomial alih-alih mempertahankan upaya yang sama.

Mari kita juga berkomitmen untuk memiliki keacakan yang sebenarnya. Anda mungkin menginginkan ini sehingga, misalnya, seseorang tidak dapat menjadwalkan liburan mereka berdasarkan algoritma deterministik sehingga mereka tidak pernah hadir ketika giliran mereka untuk membeli croissant (sampai mereka menghabiskan seluruh hari liburan mereka, saya kira) .

Jadi, ke dua jenis solusi.

1. Untuk membuat lotere yang bias, perhatikan terlebih dahulu bahwa kita dapat memilih dari hampir semua distribusi berkelanjutan (dengan penyimpangan terbatas) untuk menghasilkan angka untuk lotre kita. Yang kalah kemudian bisa menjadi orang dengan angka terendah. Maka bias yang paling sederhana adalah melacak apakah setiap individu telah membeli lebih atau kurang dari bagiannya. Anda dapat mengukur bias dalam satuan croissant. Anda dapat menyesuaikan tingkat keacakan dengan mengubah lebar dan bentuk distribusi - ini juga akan menentukan seberapa jauh setiap individu dapat memperoleh dari "jumlah waktu yang sama". Gaussians itu mudah; mereka memungkinkan untuk kejutan yang masuk akal tanpa memiliki ekor yang terlalu panjang ("tidak adil"). Jadi bentuk dasar dari solusinya adalah (dalam kode Scala)

   case class Employee(var bias: Double) {
     def eat         { bias -= 1 }
     def buy(n: Int) { bias += n }
     def roll        = bias + stdev * Random.nextGaussian
   }
   

   Anda dapat melacak siapa yang membeli terakhir dan memberi mereka bonus bias yang lumayan (mis. 10*stdev) Agar orang tidak membeli dua kali berturut-turut kecuali pada kasus tepi di mana struktur liburan memungkinkan setiap orang membeli waktu "terakhir". (yaitu Anda membeli, lalu pergi berlibur.) Hal yang sama karena tidak hadir pada hari mereka dipilih. (Jika seseorang tidak hadir setiap hari, mereka pada akhirnya akan muncul ketika mereka membakar bonus bias mereka; saya menganggap ini sebagai fitur daripada bug.)

   Jadi, Anda mengumpulkan daftar karyawan Anda saat ini untuk hari itu, minta mereka semua ikut undian, pilih yang terendah, dan perbarui. Anda dapat memilih apakah memiliki bonus pembelian sama dengan jumlah karyawan (baik ketika biaya diabaikan tetapi perjalanan untuk mendapatkan croissant memberatkan), jumlah karyawan yang hadir (baik jika perjalanan itu mudah tetapi biayanya memberatkan ), atau sesuatu di antaranya (untuk mengakui kedua beban). Mungkin lebih baik hanya memiliki hukuman "makan" untuk orang-orang yang hadir, tetapi Anda bisa melakukannya jika Anda merasa bahwa hanya berlibur tidak memberi Anda hak yang lebih sedikit.

2. Untuk membuat urutan acak yang difilter, pertama-tama Anda perlu membuat urutan acak. Mengacak daftar karyawan adalah cara yang baik untuk memulai. Ikuti saja daftarnya, secara berurutan, dari hari ke hari. Jika seseorang tidak dapat membeli karena mereka tidak ada atau tidak dapat diberitahu atau dibeli sebelumnya, lewati saja. Sekarang Anda memiliki masalah: Anda mengumpulkan orang-orang yang telah dilewati. Tapi tidak apa-apa. Ketika Anda sampai ke akhir urutan Anda, tambahkan daftar karyawan yang dilewati ke daftar lengkap sebelum mengocok. Sekarang probabilitas untuk datang sebanding dengan berapa kali Anda dilewati, yang mempertahankan properti "jumlah yang sama".

   $\log_2(N)$$N$$N!$$N^N$$\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$$N$$N=10$$~1.14$

Secara pribadi saya menyukai solusi lotre yang bias karena kontrol atas keacakan lebih baik. Dengan urutan yang difilter, Anda dapat menemukan cara yang lebih kompleks untuk menghasilkan urutan. Misalnya, daripada mengambil permutasi acak, melakukan swap lokal ke jarak tertentu, atau memungkinkan bertukar orang keluar dari kolam sepenuhnya (tetapi mereka pergi ke daftar lompatan) - tetapi hal-hal ini membutuhkan upaya yang lebih algoritmik. Dengan lotere, Anda hanya menyesuaikan standar deviasi.

$\{P_1,...,P_n\}$${v_i}^k-1$$P_i$$k$$-1$$0$

$l$$v^k=\sum_{i=1}^n ({v_i}^k)^l$

$k$$i$$1-\frac{(v_i^k)^l}{v^k}$

$P_1$

$P_1$

$v$

$v_i^k$$k$$v$$k$

$P_i$

$P_i$$k+1$$k$$P_j$$P_j$

$P_i$$v_i^k$

Dan ketika ini berlangsung selamanya, mereka hidup bahagia, berbagi harga croissant.

$P_1$$l$$l$$l=k$$l$

$P_1$$P_2$

$P_1$$v_i^k$

Ps: Maaf untuk bahasa Inggris yang buruk tapi saya bukan penutur asli dan sudah terlambat ... jangan ragu untuk memperbaiki kesalahan (dan mungkin menambahkan begitu bumbu pada cerita ...)

Setiap iterasi yang Anda miliki

• Daftar orang yang hadir dan tersedia untuk membeli
• Pembeli sebelumnya

Jika Anda memilih seseorang secara acak di antara orang-orang dalam daftar dan mengecualikan pembeli sebelumnya, Anda mencapai tujuan Anda:

1. Algoritma ini "secara maksimal" acak karena kami menggunakan jumlah minimum informasi dari iterasi sebelumnya dan memilih secara acak.
2. Rata-rata orang membayar croissant (N / (N-1)) setiap kali mereka berpartisipasi dalam ekstraksi yang membuat algoritma seadil mungkin.
3. Saya akan menyarankan untuk menghilangkan aturan no-repeat untuk membuat ini secara acak maksimal.

Algoritme lain yang saya lihat diusulkan kurang acak atau kurang adil:

1. Algoritma "Deck shuffle" tidak benar-benar acak dalam arti bahwa probabilitas untuk harus membayar tidak konstan (1 / N di pick pertama, 1 / (N-1) di kedua ... 1 di pick Nth - - jika belum diambil). Selain itu, jika Anda memilih pertama, Anda memiliki peluang nol untuk diambil untuk N kali berikutnya. Sistem ini mudah rusak dengan jarang masuk sampai dipetik dan kemudian terus-menerus.

2. Algoritma "Kompensatif" yang mencoba secara aktif membuat semua orang mendapatkan jumlah croissant yang sama alih-alih mengandalkan properti nomor acak gagal menjadi acak atau adil (atau keduanya).