Cari tahu giliran siapa yang membeli croissant, yang menghitung kemungkinan absen

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 tidak masalah.

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 1: Cari tahu siapa yang akan membeli croissant oleh Florian Margaine.
Asal 2: Cari tahu siapa yang akan membeli croissant oleh Gilles.
Pertanyaan ini adalah versi yang sama dengan Gilles, dan telah diposting ulang pada Programmer sebagai percobaan untuk melihat bagaimana komunitas yang berbeda menghadapi tantangan pemrograman.}

Saya akan menggunakan algoritma penilaian. Setiap orang mulai dengan skor nol. Setiap kali mereka membawa croissant, menambah skor mereka dengan 1. Skor semua anggota tim yang tidak membawa croissant dikurangi dengan 1 / N. Jadi skor 0 berarti bahwa seorang anggota tim tidak memiliki kelebihan atau kekurangan.

Tanpa keacakan, pilih orang dengan skor terendah dari daftar mereka yang akan hadir.

Untuk menambahkan keacakan, urutkan daftar berdasarkan skor dan pilih secara acak dari daftar semua anggota tim dengan skor negatif. Dengan membatasi nilai negatif, Anda memastikan tidak ada yang terlalu "beruntung" selama berminggu-minggu.

Keuntungan dari algoritma ini adalah tidak memiliki ketergantungan untuk menyimpan catatan sejarah dan dengan mudah memungkinkan penambahan anggota tim baru di setiap titik waktu.

Ini dapat diadaptasi untuk memungkinkan absen relatif umum dengan mengurangi skor hanya mereka yang hadir untuk menikmati croissant.

Apa yang akan saya lakukan, jika saya harus mengambil ini, adalah mengambil topi, dan meletakkan nama semua orang di topi itu sekali di selembar kertas kecil. Kemudian setiap hari, saya akan mengambil nama seseorang dari topi secara acak, dan itulah orang yang membawa croissant keesokan harinya. Makalah itu kemudian ditempel di papan, di bawah "MEMBAWA CROISSANTS TOMORROW". Kertas yang saat ini ada di papan akan dibuang.

Saya juga punya kotak. Itu mulai kosong. Setiap hari, sebelum menggambar nama-nama itu, saya akan membuang isi kotak itu ke dalam topi, kemudian memeriksa kertas-kertas dalam topi itu dan menyingkirkan semua orang yang akan absen besok. Nama mereka ada di dalam kotak.

Jika tiba waktunya untuk menggambar nama dan topinya kosong, saya akan merobek beberapa kertas lagi dan menambahkan nama semua orang sekali, kemudian memindahkan nama-nama semua orang yang akan absen besok ke kotak.

Karena dua langkah terakhir ini, dimungkinkan untuk nama yang sama berada di topi beberapa kali sekaligus. Jika nama yang saya gambar sama dengan nama yang ada di papan tulis, saya akan memindahkan kertas itu ke kotak, dan kemudian menggambar lagi.

Seharusnya tidak terlalu sulit untuk menerjemahkan sistem ini ke algoritme dalam bahasa pilihan Anda.

Algoritma, smalgorithm. Gunakan DB.

create table team_members 
(
    id integer auto_increment,
    name varchar(255),
    purchase_count integer,
    last_purchase_date datetime,
    present integer,
    prefers_donuts integer default 0,
    primary key( id)
)

Siapa yang beli?

select id from team_members where (present = 1) and (prefers_donuts = 0) order by purchase_count, last_purchase_date limit 1;

Setelah mereka membeli:

update team_members set purchase_count = purchase_count + 1, last_purchase_date = now() where id = ?

Dan kemudian atur:

insert into team_members (name, prefers_donuts) values ('GrandmasterB', 1);

... karena saya sekolah tua.

Seharusnya tidak terlalu sulit untuk menambahkan sedikit keacakan dengan mengubah kueri pertama - mungkin dengan menambahkan acak () alih-alih mengurutkan berdasarkan tanggal last_purchase.

Saya sebenarnya harus menyelesaikan masalah ini di dunia nyata:

remember how many times people have gotten donuts
every day:
  var candidates = everyone
  toss out people who aren't here tomorrow
  toss out people who aren't here today 
  toss out the person who got them today (unless they're the only one left)
  toss out everyone where "times they got donuts"/"times everyone has got donuts"
    is more than 1/number of people (unless that would eliminate everyone)

  pick someone at random from the candidates

Apa yang terjadi adalah orang-orang yang telah membeli donat "terlalu banyak" (karena nasib buruk, akan bekerja ketika orang lain sedang berlibur, dll) dikeluarkan dari kolam sampai akuisisi cukup berlalu untuk menempatkan mereka kembali di bawah persentase "benar" dari pembelian.

Ini perlu diperluas untuk menangani perekrutan orang baru dengan lebih baik ...

Bagaimanapun, desain ini bekerja sangat baik untuk mengubah variabel (siapa yang ada, siapa yang keluar) dan ketika jadwal harus (praktis) tak terbatas. Sebagai bonus tambahan, mudah membuat deterministik dengan menyemai RNG Anda.

Tidak sebagus beberapa jawaban lain yang sudah disajikan, tetapi cara lain untuk melihat masalah:

1. Buat daftar semua karyawan yang berpartisipasi
2. Gandakan daftar berkali-kali (misalnya, 1.000)
3. Kocok daftar

Setiap sore, pilih pembawa croissant berikutnya yang tersedia. Setiap pagi, pembawa croissant menyilangkan namanya di bagian atas daftar.

Pemrosesan harian adalah pena & kertas sederhana.

Karyawan Baru & Pengakhiran Alumni mungkin akan ditangani dengan membuat daftar baru. Jika siklus CPU menjadi mahal lagi (atau Anda memiliki 100 juta karyawan & hanya Arduino gen 1) maka akan mudah untuk memberi garam pada daftar asli dengan jumlah tempat pemegang yang sesuai.

Info lebih lanjut (per permintaan).

Menggunakan pendekatan ini dengan daftar panjang yang sewenang-wenang, Anda mendapatkan manfaat dari transparansi.

Anda tidak hanya tahu siapa yang akan membawa croissant besok, Anda tahu siapa yang dijadwalkan untuk membawa mereka di hari berikutnya, dan seterusnya. Tentu saja semakin jauh dalam waktu Anda terlihat kurang akurat Anda akan karena absen, dll.

Devs licik yang mencari cara menimbang slip kertas mereka di topi tidak akan memiliki banyak kesempatan untuk menghindari tugas membawa croissant mereka.

Merengek non-devs yang mengklaim diproses diproses dengan mudah dapat meninjau data, menghasilkan kesimpulan yang salah, dan tetap merengek.

Tidak acak

Pertahankan daftar yang dipesan. Jika seseorang absen pada hari mereka seharusnya membeli, tukar mereka dengan orang yang tersedia berikutnya. Akhirnya orang tersebut akan hadir dan membeli croissant. Jadi, isi daftar tetap sama, tetapi orang dapat dipindahkan atau naik tergantung pada absen.

Orang baru dimasukkan ke daftar setelah posisi saat ini. Orang yang berhenti atau berhenti dihapus dari daftar. Posisi saat ini bertambah 1 setiap hari, ketika mencapai akhir, itu akan kembali ke awal.

Ini mengasumsikan ada cukup banyak orang dalam daftar untuk memperhitungkan rata-rata waktu absen untuk mempromosikan keadilan.

Acak

Kita tidak bisa hanya memilih orang secara acak setiap hari karena akan ada bias jangka pendek, misalnya membalik koin 10 kali dan Anda bisa muncul kepala 8 dan ekor 2, sehingga kepala akan kacau untuk jangka pendek. Jadi, kita perlu membuat ember orang agar tetap adil.

Ember ditentukan oleh berapa kali orang membeli crossiants di masa lalu. Jadi, dalam hal ini, kami akan menyimpan kamus orang dan membeli crossiant. Pada hari 1 semua orang dalam ember nol. Ketika orang membeli croissiant, mereka akan ditugaskan ke ember berikutnya, yaitu 1, 2, dll. Bagian acak mengambil dari kumpulan orang yang tersedia dalam ember. Ember pertama yang tersedia adalah ember dengan pembelian paling sedikit. Jika ada 10 orang di dalam ember, maka pilih nomor acak dari 1 hingga 10 dan siapa yang membeli croissant. Orang-orang baru diberi ember terendah saat ini sehingga mereka tidak membeli putaran crossiants (meskipun mereka akan segera berada di daftar pembelian). Jika tidak ada yang tersedia di ember terendah (semuanya tidak ada), maka Anda pergi ke ember tertinggi berikutnya. Misalnya, mari S mengatakan ada daftar 10 orang. Pada hari ke 8, 8 orang berada di ember 1 dan 2 ada di ember 0. Kedua orang di ember 0 tidak ada. Dalam hal ini, ember 1 akan digunakan dan satu orang akan berakhir di ember 2. Tetapi, orang akan selalu berada dalam beberapa pembelian crossiant (ember) satu sama lain, karena orang yang sekarang berada di ember 2 kemungkinan besar tidak akan berada dalam ember beli kolam untuk sementara waktu.

Tweaks dapat ditambahkan untuk memastikan orang yang sama tidak membeli dua hari berturut-turut dan ada beberapa kasus tepi untuk ditangani, tetapi ini akan menambah elemen keacakan serta menjaganya tetap adil. Selain itu, orang mungkin ingin menjaga agar croissant yang sebenarnya dibandingkan dengan ember saat ini terpisah. Ketika orang pergi, ada yang dihapus dari ember dengan menandai mereka secara permanen tidak ada atau menghapusnya sama sekali.