Rozwiń Problem uczennicy Kirkmana

22

Dla tych z was, którzy nie są zaznajomieni, problem uczennicy Kirkmana wygląda następująco:

Piętnaście młodych kobiet w szkole wychodzi z domu trzy kolejne przez siedem dni z rzędu: należy je tak ustawiać codziennie, aby żadna z dwóch nie poszła dwa razy do przodu.

Możemy spojrzeć na to jak zagnieżdżoną listę 3 na 5 (lub macierz):

[[a,b,c]
 [d,e,f]
 [g,h,i]
 [j,k,l]
 [m,n,o]]

Zasadniczo celem pierwotnego problemu jest wymyślenie 7 różnych sposobów ułożenia powyższej matrycy, tak aby dwie litery nigdy nie dzieliły wiersza więcej niż jeden raz . W MathWorld (link powyżej) znajdujemy to rozwiązanie:

[[a,b,c]   [[a,d,h]   [[a,e,m]   [[a,f,i]   [[a,g,l]   [[a,j,n]   [[a,k,o]
 [d,e,f]    [b,e,k]    [b,h,n]    [b,l,o]    [b,d,j]    [b,i,m]    [b,f,g]
 [g,h,i]    [c,i,o]    [c,g,k]    [c,h,j]    [c,f,m]    [c,e,l]    [c,d,n]
 [j,k,l]    [f,l,n]    [d,i,l]    [d,k,m]    [e,h,o]    [d,o,g]    [e,i,j]
 [m,n,o]]   [g,j,m]]   [f,j,o]]   [e,g,n]]   [i,k,n]]   [f,h,k]]   [h,l,m]]

A gdyby tak była inna liczba uczennic? Czy może być ósmy dzień? To jest nasze wyzwanie.

W tym przypadku nie †† , ale niekoniecznie dla innych wymiarów tablicy
†† Możemy to łatwo pokazać, ponieważ apojawia się w rzędzie z każdą inną literą.


Wyzwanie:

Biorąc pod uwagę wejście wymiarów (wierszy niż kolumn) tablicy uczennic (czyli 3 x 5, 4 x 4czy [7,6], [10,10]itp), wyjście największy możliwy zestaw „dni”, które odpowiadają wymaganiom określonym powyżej.

Dane wejściowe:
wymiary tablicy uczennicy (dowolna rozsądna forma wprowadzania, którą chcesz).

Wyjście:
największa możliwa seria tablic spełniająca powyższe wymagania (dowolna rozsądna forma).

Przypadki testowe:

Input:  [1,1]
Output: [[a]]

Input:  [1,2]
Output: [[a,b]]

Input:* [2,1]
Output: [[a]
         [b]]

Input:  [2,2]
Output: [[a,b]  [[a,c]  [[a,d]
         [c,d]]  [b,d]]  [b,c]]

Input:  [3,3]
Output: [[a,b,c]  [[a,d,g]  [[a,e,i]  [[a,f,h]
         [d,e,f]   [b,e,h]   [b,f,g]   [b,d,i]
         [g,h,i]]  [c,f,i]]  [c,d,h]]  [c,e,g]]

Input:  [5,3]
Output: [[a,b,c]   [[a,d,h]   [[a,e,m]   [[a,f,i]   [[a,g,l]   [[a,j,n]   [[a,k,o]
         [d,e,f]    [b,e,k]    [b,h,n]    [b,l,o]    [b,d,j]    [b,i,m]    [b,f,g]
         [g,h,i]    [c,i,o]    [c,g,k]    [c,h,j]    [c,f,m]    [c,e,l]    [c,d,n]
         [j,k,l]    [f,l,n]    [d,i,l]    [d,k,m]    [e,h,o]    [d,o,g]    [e,i,j]
         [m,n,o]]   [g,j,m]]   [f,j,o]]   [e,g,n]]   [i,k,n]]   [f,h,k]]   [h,l,m]]

There may be more than one correct answer. 

* Dzięki @Frozenfrank za poprawienie przypadku testowego 3 : jeśli jest tylko jedna kolumna, może być tylko jeden dzień, ponieważ kolejność wierszy nie ma znaczenia.

To zawody w - wygrywa najkrótsza odpowiedź.

Scott Milner
źródło
Czy odnosi się to w jakiś sposób do skończonych płaszczyzn rzutowych, czy mam na myśli inny problem?
Neil,
@ Nee Nie mam pojęcia. Obawiam się, że nie mam kwalifikacji, by na to odpowiedzieć. ;-)
Scott Milner,
Czy istnieje limit czasowy?
Artyer
@Artyer Nie, ale chciałbym móc przetestować kod ...
Scott Milner
2
@Neil to była zabawna lektura Wikipedii.
Magic Octopus Urn

Odpowiedzi:

12

Mathematica, 935 bajtów

Inp={5,4};L=Length;T=Table;ST[t_,k_,n_]:=Binomial[n-1,t-1]/Binomial[k-1,t-1];H=ToExpression@Alphabet[];Lo=Inp[[1]]*Inp[[2]];H=H[[;;Lo]];Final={};ST[2,3,12]=4;ST[2,4,20]=5;If[Inp[[2]]==1,Column[Partition[H,{1}]],CA=Lo*Floor@ST[2,Inp[[2]],Lo];While[L@Flatten@Final!=CA,Final={};uu=0;S=Normal[Association[T[ToRules[H[[Z]]==Prime[Z]],{Z,L@H}]]];PA=Union[Sort/@Permutations[H,{Inp[[2]]}]];PT=Partition[H,Inp[[2]]];While[L@PA!=0,AppendTo[Final,PT];Test=Flatten@T[Times@@@Subsets[PT[[X]],{2}]/.S,{X, L@PT}];POK=T[Times@@@Subsets[PA[[Y]],{2}]/.S,{Y,L@PA}];Fin=Select[POK,L@Intersection[Test,#]==0&];Facfin=T[FactorInteger[Fin[[V]]],{V,L@Fin}];end=T[Union@Flatten@T[First/@#[[W]],{W,L@#}]&[Facfin[[F]]],{F,L@Facfin}]/.Map[Reverse,S];PA=end;PT=DeleteDuplicates[RandomSample@end,Intersection@##=!={}&];If[L@Flatten@PT<L@H,While[uu<1000,PT=DeleteDuplicates[RandomSample@end,Intersection@##=!={}&];If[L@Flatten@PT==L@H,Break[],uu++]]]]];Grid@Final]


dotyczy to maksymalnie 26 kobiet

EDYCJA
Wprowadziłem kilka zmian i myślę, że to działa! Kod jest teraz ustawiony do rozwiązania [5,4] (co jest „problemem graczy w golfa społecznościowego”) i uzyskuje wynik w ciągu kilku sekund. Jednak [5,3] problem jest trudniejszy i będziesz musiał poczekać 10-20 minut, ale otrzymasz odpowiednią kombinację na wszystkie dni. W przypadku łatwiejszych przypadków jest to bardzo szybkie.

w każdym razie możesz wypróbować i zobaczyć wyniki
Wypróbuj online tutaj
skopiuj i wklej za pomocą ctrl-v
naciśnij shift + enter, aby uruchomić kod
możesz zmienić dane wejściowe na początku kodu -> Inp = {5,4}
uruchom koduj wiele razy, aby uzyskać różne permutacje

J42161217
źródło
Chociaż jest to imponujące i robi duży postęp w kierunku rozwiązania problemu, wciąż jest niekompletne. Chociaż działa dla mniejszych przypadków testowych, nie mógł rozwiązać większych, w tym [5,3]przypadku testowego, na którym opiera się cały problem. Ponadto można więcej grać w golfa; istnieje kilka nazw zmiennych, które są większe, niż muszą być, a niektóre funkcje można skrócić za pomocą @notacji lub infiksu. Mam jednak nadzieję, że nadal będziesz pracować!
Scott Milner,
dzięki za sprawdzenie. Postaram się, aby najpierw zadziałało, a potem w golfa ...
J42161217
1
Powinieneś być w stanie zaoszczędzić wiele bajtów, tworząc nazwy zmiennych w postaci pojedynczych liter i przypisując niektóre funkcje, których używasz więcej niż jeden raz, i zastępując funkcje tymi zmiennymi :)
numbermaniac
2
@numbermaniac Po prostu zastępując nazwy zmiennych, udało mi się to sprowadzić 914. Gra powinna być golfowa do około 850.
Scott Milner
3
Naprawiłem przypadek testowy. Przede wszystkim chcę, żeby to działało. Dlatego jeszcze nie grałem w golfa. Dziękujemy za wszystkie komentarze. Myślę, że teraz jest gotowy.
J42161217