Pengaturan tempat duduk yang baik untuk urutan makanan dan tabel ukuran k untuk sekelompok orang

Diberikan seperangkat $S$ orang yang saya ingin duduk mereka untuk urutan makanan di meja ukuran $k$ . (Tentu saja, ada cukup meja untuk duduk semua $|S|$ untuk setiap makan.) Saya ingin mengatur ini sehingga tidak ada yang berbagi meja dengan orang yang sama dua kali. Nilai tipikal adalah $|S|=45$ dan $k=5$ dan 6 hingga 10 kali makan.

Dengan cara yang lebih abstrak, saya ingin menemukan urutan partisi $S$ sedemikian sehingga setiap partisi terdiri dari himpunan bagian kardinalitas berpasangan berpasangan $k$dan properti global tambahan yang setiap persimpangan antara dua himpunan bagian tersebut tidak mengandung lebih dari satu elemen. Saya menduga ini dapat dirumuskan sebagai masalah teoritis atau kombinatorik grafik.

Saya akan berterima kasih untuk perumusan masalah yang lebih baik dan menunjuk ke literatur yang relevan karena berada di luar domain saya.

Latar belakang: ini dapat digunakan untuk pengaturan tempat duduk di Schloss Dagstuhl di mana banyak ilmuwan komputer datang untuk membahas penelitian mereka selama seminggu. Saat ini tempat duduk dilakukan secara acak dan tidak mengejutkan beberapa orang mendapati dirinya duduk dengan orang yang sama dua kali (atau lebih sering) selama seminggu. Juga tidak mengejutkan, kami menerima beberapa keluhan tentang ini dan saran samar-samar bagaimana memperbaikinya. Saya ingin memahami ini lebih baik. Perumusan masalah yang lebih kuat melibatkan pengoptimalan siapa yang duduk di sebelah satu sama lain, tetapi saya percaya ini tidak relevan untuk tabel ukuran 5.

Di luar aplikasi saya pikir pertanyaan menarik adalah untuk jumlah maksimum makanan yang dapat dilayani untuk $S$ dan diberikan $k$, yaitu, berapa banyak partisi seperti itu ada.

Berikut varian jawaban asli (di bawah) yang memberikan pengaturan yang diinginkan: tabel ukuran 5, 45 orang, dan 10 kali makan, kecuali satu kali makan memiliki beberapa tabel ukuran 4.

Biarkan menjadi bidang ukuran 9. Pilih 4 garis vertikal, merosot { ( b , x ) | x ∈ F $F$$\{(b,x) | x \in F\}$ untuk setiap dan menyatakan orang mereka "kosong." Kita dibiarkan dengan 81 - 9x4 = 45 orang.$b = 0,1,2,3$

9 makanan diberikan oleh lereng . Persimpangan dengan 4 garis degenerasi kosong mengurangi ukuran tabel menjadi 9-4 = 5.$a = 0,1,\ldots,8$

Makanan tambahan diberikan oleh garis degenerasi yang tersisa untuk setiap b $\{(b,x) | x \in F\}$ . Di sini ukuran tabel adalah 9. Namun (dalam solusi apa pun) kita dapat memecah tabel ukuran 9 menjadi tabel ukuran 5 dan satu ukuran 4.$b = 4,5,6,7,8$

Jika ada beberapa orang lagi yang dapat menggunakan bidang ukuran 11.

Pertama mari kita menangani orang dan k makan.$k^2$$k$

Pilih bidang yang terbatas $F$ ukuran dan mengidentifikasi orang-orang dengan F × F . Untuk setiap makanan ada sesuai dengan kemiringan, ke meja garis sejajar dengan kemiringan itu.$k$$F \times F$

Secara khusus, makan memiliki k tabel { ( x , a x + b ) | x $a$$k$ untuk setiap b ∈ F .$\{(x,ax+b) | x \in F\}$$b \in F$

Properti persimpangan yang Anda inginkan adalah kenyataan bahwa garis-garis dengan kemiringan yang berbeda berpotongan tepat pada satu titik.

Untuk menangani orang, bagilah dalam dua kelompok masing-masing k 2 , dan terapkan konstruksi di atas untuk masing-masing kelompok. Untuk menangani 2 k 2 - k = 45 , beri label (pada kelompok pertama) saluran tetap seperti { ( x , x ) | x $2k^2$$k^2$$2k^2 - k = 45$ sebagai "kosong." Anda mungkin memiliki beberapa meja dengan k - 1 orang.$\{(x,x)|x\in F\}$$k-1$

Untuk makan lebih banyak, misalnya, dapat memilih partisi yang berbeda dalam dua kelompok pada awal makanan ke-6. (Katakan Anda interleave partisi asli, untuk memastikan bahwa kedua kelompok "campuran.") Meskipun tentu saja ini dapat menghasilkan beberapa persimpangan.

Inilah batas (longgar?) Pada jumlah makanan yang bisa Anda sajikan.

Biarkan dan menganggap bahwa n dapat dibagi dengan k . Juga, asumsikan bahwa Anda memiliki meja persis n / k dan Anda ingin setiap meja penuh selama makan.$|S| = n$$n$$k$$n/k$

Untuk setiap makan, buat grafik dengan simpul untuk setiap orang di dan tepi ketika dua orang berbagi meja. Grafik ini adalah kumpulan klik-klik n / k yang masing-masing berukuran k . Dengan demikian jumlah tepi dalam grafik adalah Θ ( n k ) .$S$$n/k$$k$$\Theta(nk)$

Karena Anda tidak ingin ada tepi yang muncul dalam dua makanan yang berbeda, dan karena jumlah total tepi yang mungkin pada set simpul ukuran adalah Θ ( n 2 ) , ini menunjukkan Anda hanya dapat menyajikan O ( n $n$$\Theta(n^2)$ makanan .$O(n/k)$

Sebenarnya, tidak sulit untuk menemukan konstanta di sini dan ketika Anda menghitung, Anda mendapatkan batas atas tepat $\frac{n-1}{k-1}$ , yang, untuk nilai tipikal Anda, adalah 11.

Jika Anda ingin dua orang duduk di meja yang sama persis sekali, maka ini disebut desain 2 yang dapat diselesaikan dan telah banyak dipelajari. Tentu saja membiarkan melewatkan beberapa kali makan akan memberikan solusi untuk masalah Anda ketika dua orang dapat bertemu paling banyak satu kali. (Tapi solusi lain mungkin ada, saya kira.)

Saya tidak yakin apakah Anda memerlukan algoritma deterministik, tetapi saya telah memecahkan masalah serupa di masa lalu menggunakan metode rantai Markov Monte Carlo .

Anda dapat melihat contoh kerja dari pendekatan ini di Github - program ini berupaya untuk menempatkan sekelompok orang di meja dengan ukuran tetap, mengingat serangkaian batasan tempat duduk yang mungkin positif atau negatif ("harus" atau "tidak boleh" ), dan baik absolut atau relatif ("lebih disukai").

Catatan: program ini tidak memecahkan masalah yang sama persis dengan yang Anda usulkan, tetapi program ini memberikan demonstrasi kerja metode rantai Monte Carlo Markov, dan cukup dekat sehingga Anda dapat dengan mudah menyesuaikannya sesuai kebutuhan untuk masalah Anda.

Program ini memecahkan masalah untuk satu kali makan malam, tetapi dalam kasus Anda, cara mudah untuk mendekati masalah adalah dengan menjalankan algoritma satu kali untuk setiap makan malam, setiap kali menyediakan teman sebelumnya masing-masing pengunjung sebagai persyaratan fuzzy atau negatif mutlak. (Keuntungan dari persyaratan fuzzy adalah Anda dijamin bahwa algoritme akan berhenti pada semua input, bahkan jika pengaturan yang sempurna tidak dapat ditemukan).

Dalam proses ini, kami pertama-tama akan mencoba untuk mendudukkan setiap pengunjung sesuai dengan persyaratan absolut - Anda mungkin ingin melewati bagian proses ini, karena hanya berfungsi ketika persyaratan absolut jumlahnya relatif kecil; jika tidak, Anda akan berakhir dengan masalah yang sangat besar !

Pada langkah berikutnya, kami membuat serangkaian tabel dan menetapkan peserta secara acak ke tabel untuk konfigurasi awal, dan skor dihitung untuk mewakili jumlah persyaratan fuzzy yang telah dipenuhi. Pasangan pengunjung dinyalakan secara acak, dan skor dihitung ulang untuk tabel tersebut untuk menentukan apakah konfigurasi baru lebih disukai.

Bagian dari proses ini idealnya harus diulangi dengan beberapa konfigurasi awal, dan dapat dengan mudah dihitung secara paralel.

Saya pikir pengaturan tempat duduk yang valid sama dengan hypergraph d-reguler di | S | simpul, di mana d adalah jumlah makan malam, dengan peringkat paling banyak k dan maksimum codegree 1. Solusi sepele adalah membuat semua orang selalu duduk sendiri, tapi saya kira tujuannya adalah untuk meminimalkan jumlah tabel?