İnsanları gruplara atamak için kombinatoryal algoritma

Question

Bir iş arkadaşım bana ilginç bir problemle geldi, pratik bir tanesi "şehirdeki yeni insanlar" grubu ile ilgili bir parçası.

18 arkadaş, önümüzdeki 4 güne ait gruplar için akşam yemeği yemek ister.

1. Her gün grup insanın herhangi verilen çifti sadece boyunca en fazla bir kez birbirlerini görecek 4 4 gruba bölünür ve 2.
2. bir grup olacaktır: şöyle kurallardır 4 gün.
3. Herhangi bir kişi, en fazla bir defada yalnızca boyut 2 grubunun bir parçası olacaktır.

Geçerli grup ataması için kaba kuvvet özyinelemeli arama açıkçası pratik değildir. Ağacın parçalarını mümkün olan en kısa sürede budamak için bazı basit mantıklara atıldım, ama bunu pratik hale getirmek için yeterli değil. Aslında, tüm kurallara uymanın imkansız olabileceğinden şüphe etmeye başladım, ama bunun neden olabileceğine dair bir kombinatoryal argüman oluşturamıyorum.

Herhangi bir düşünce?

Answer 1

16 arkadaş, 4 gece için, iki adet mutually orthogonal latin squares siparişini kullanarak 4 gece planlanabilir. 4. Arkadaşlarınızı 4x4 ızgarasında farklı bir konuma atayın. İlk gece, sıraya göre grup. İkinci olarak, grup sütununa göre. Üçüncü grupta, latin kare # 1'de benzer girişe göre grup (4x4 örneğinde kart sıralaması). Dördüncü grupta, latin kare # 2'ye benzer bir girişle grup (4x4 örneğinde kart takımı). Aslında, afinite düzlemi inşaatı üç karşılıklı ortogonal latin kareye yükselir, bu nedenle beşinci bir gece planlanabilir, böylece her bir arkadaş çifti bir kez tam olarak bir araya gelir. Kullanılmayan beşinci gecenin özgürlüğü kullanılarak belki de 16 için program uzatılabilirdi.

DÜZENLEME: İşte 5 geceden fazla 16 kişi için program. Her sıra bir gece. Her sütun bir kişidir. Giriş, atanmış oldukları gruptur.

[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 
[0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3] 
[0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 0, 1, 3, 2, 1, 0] 
[0, 2, 3, 1, 1, 3, 2, 0, 2, 0, 1, 3, 3, 1, 0, 2] 
[0, 3, 1, 2, 1, 2, 0, 3, 2, 1, 3, 0, 3, 0, 2, 1]