do
Wprowadzenie
Jak skomentował David Carraher, najprostszym sposobem analizy płytki sześciokątnej wydaje się być wykorzystanie jej izomorfizmu z trójwymiarowym diagramem Younga, zasadniczo kwadratem x, y wypełnionym całkowitymi słupkami wysokości, których wysokości muszą pozostać takie same lub wzrosnąć w miarę zbliżania się do osi Z.
Zacząłem od algorytmu znajdowania sum, który jest bardziej podatny na dostosowanie do zliczania symetrii niż opublikowany algorytm, który opiera się na odchyleniu do jednej z trzech osi kartezjańskich.
Algorytm
Zaczynam od wypełnienia komórek płaszczyzn x, y i z 1, podczas gdy reszta obszaru zawiera zera. Gdy to zrobisz, buduję wzór warstwa po warstwie, przy czym każda warstwa zawiera komórki, które mają wspólną odległość 3D manhattan od początku. Komórka może zawierać tylko 1, jeśli trzy komórki poniżej również zawierają 1. jeśli którakolwiek z nich zawiera 0, wówczas komórka musi być 0.
Zaletą budowania wzoru w ten sposób jest to, że każda warstwa jest symetryczna względem linii x = y = z. Oznacza to, że każdą warstwę można sprawdzić niezależnie pod kątem symetrii.
Sprawdzanie symetrii
Symetrie bryły są następujące: 3-krotny obrót wokół linii x = y = z -> 3-krotny obrót wokół środka sześciokąta; oraz 3 x odbicia o 3 płaszczyznach zawierających linię x = y = z i każdą z osi x, y, z -> odbicie o liniach przechodzących przez narożniki sześciokąta.
Daje to tylko 6-krotną symetrię. Aby uzyskać pełną symetrię sześciokąta, należy rozważyć inny rodzaj symetrii. Każda bryła (zbudowana z 1) ma komplementarną bryłę (zbudowana z 0). Gdy N jest nieparzyste, bryła uzupełniająca musi różnić się od oryginalnej bryły (ponieważ nie jest możliwe, aby miały taką samą liczbę kostek). Jednak gdy komplementarna bryła zostanie obrócona, okaże się, że jej reprezentacja 2D jako płytki diamentowej jest identyczna (z wyjątkiem 2-krotnej operacji symetrii) z oryginalną bryłą. Tam, gdzie N jest parzyste, możliwe jest, że ciało stałe jest samo-odwrotne.
Można to zobaczyć w przykładach dla N = 2 w pytaniu. Patrząc od lewej strony, pierwszy sześciokąt wygląda jak solidny sześcian z 8 małymi kostkami, podczas gdy ostatni sześciokąt wygląda jak pusta skorupa z 0 małymi kostkami. Patrząc z prawej strony, sytuacja jest odwrotna. Sześciokąty 3, 4 i 5 oraz 16, 17 i 18 sześciokąty wyglądają tak, jakby zawierały 2 lub 6 kostek, a zatem uzupełniają się w 3 wymiarach. Są one powiązane ze sobą w 2 wymiarach za pomocą 2-krotnej operacji symetrii (2-krotny obrót lub odbicie wokół osi przez krawędzie sześciokąta). Z drugiej strony, 9, 10, 11 i 12 sześciokąty pokazują wzory 3D, które są ich własnymi uzupełnieniami, a zatem mają wyższą symetrię (dlatego są to jedyne wzorce o nieparzystej krotności).
Zauważ, że posiadanie (N ^ 3) / 2 kostek jest warunkiem koniecznym do samouzupełniania się, ale ogólnie nie jest warunkiem wystarczającym, jeśli N> 2. Wynikiem tego wszystkiego jest to, że w przypadku nieparzystego N przechylenie zawsze występuje w parach (N ^ 3) / 2 kostki należy dokładnie sprawdzić.
Bieżący kod (generuje właściwą sumę dla N = 1,2,3,5. Błąd, jak omówiono dla N = 4).
int n; //side length
char t[11][11][11]; //grid sized for N up to 10
int q[29][192], r[29]; //tables of coordinates for up to 10*3-2=28 layers
int c[9]; //counts arrangements found by symmetry class. c[8] contains total.
//recursive layer counting function. m= manhattan distance, e= number of cells in previous layers, s=symmetry class.
void f(int m,int e,int s){
int u[64], v[64], w[64]; //shortlists for x,y,z coordinates of cells in this layer
int j=0;
int x,y,z;
for (int i=r[m]*3; i; i-=3){
// get a set of coordinates for a cell in the current layer.
x=q[m][i-3]; y= q[m][i-2]; z= q[m][i-1];
// if the three cells in the previous layer are filled, add it to the shortlist u[],v[],w[]. j indicates the length of the shortlist.
if (t[x][y][z-1] && t[x][y-1][z] && t[x-1][y][z]) u[j]=x, v[j]=y, w[j++]=z ;
}
// there are 1<<j possible arrangements for this layer.
for (int i = 1 << j; i--;) {
int d = 0;
// for each value of i, set the 1's bits of t[] to the 1's bits of i. Count the number of 1's into d as we go.
for (int k = j; k--;) d+=(t[u[k]][v[k]][w[k]]=(i>>k)&1);
// we have no interest in i=0 as it is the empty layer and therefore the same as the previous recursion step.
// Still we loop through it to ensure t[] is properly cleared.
if(i>0){
int s1=s; //local copy of symmetry class. 1's bit for 3 fold rotation, 2's bit for reflection in y axis.
int sc=0; //symmetry of self-complement.
//if previous layers were symmetrical, test if the symmetry has been reduced by the current layer
if (s1) for (int k = j; k--;) s1 &= (t[u[k]][v[k]][w[k]]==t[w[k]][u[k]][v[k]]) | (t[u[k]][v[k]][w[k]]==t[w[k]][v[k]][u[k]])<<1;
//if exactly half the cells are filled, test for self complement
if ((e+d)*2==n*n*n){
sc=1;
for(int A=1; A<=(n>>1); A++)for(int B=1; B<=n; B++)for(int C=1; C<=n; C++) sc&=t[A][B][C]^t[n+1-A][n+1-B][n+1-C];
}
//increment counters for total and for symmetry class.
c[8]++; c[s1+(sc<<2)]++;
//uncomment for graphic display of each block stacking with metadata. not recommended for n>3.
//printf("m=%d j=%d i=%d c1=%d-2*%d=%d c3=%d cy=%d(cs=%d) c3v=%d ctot=%d\n",m,j,i,c[0],c[2],c[0]-2*c[2],c[1],c[2],c[2]*3,c[3],c[8]);
//printf("m=%d j=%d i=%d C1=%d-2*%d=%d C3=%d CY=%d(CS=%d) C3V=%d ctot=%d\n",m,j,i,c[4],c[6],c[4]-2*c[6],c[5],c[6],c[6]*3,c[7],c[8]);
//for (int A = 0; A<4; A++, puts(""))for (int B = 0; B<4; B++, printf(" "))for (int C = 0; C<4; C++) printf("%c",34+t[A][B][C]);
//recurse to next level.
if(m<n*3-2)f(m + 1,e+d,s1);
}
}
}
main()
{
scanf("%d",&n);
int x,y,z;
// Fill x,y and z planes of t[] with 1's
for (int a=0; a<9; a++) for (int b=0; b<9; b++) t[a][b][0]= t[0][a][b]= t[b][0][a]= 1;
// Build table of coordinates for each manhattan layer
for (int m=1; m < n*3-1; m++){
printf("m=%d : ",m);
int j=0;
for (x = 1; x <= n; x++) for (y = 1; y <= n; y++) {
z=m+2-x-y;
if (z>0 && z <= n) q[m][j++] = x, q[m][j++] = y, q[m][j++]=z, printf(" %d%d%d ",x,y,z);
r[m]=j/3;
}
printf(" : r=%d\n",r[m]);
}
// Set count to 1 representing the empty box (symmetry c3v)
c[8]=1; c[3]=1;
// Start searching at f=1, with 0 cells occupied and symmetry 3=c3v
f(1,0,3);
// c[2 and 6] only contain reflections in y axis, therefore must be multiplied by 3.
// Similarly the reflections in x and z axis must be subtracted from c[0] and c[4].
c[0]-=c[2]*2; c[2]*=3;
c[4]-=c[6]*2; c[6]*=3;
int cr[9];cr[8]=0;
printf("non self-complement self-complement\n");
printf("c1 %9d/12=%9d C1 %9d/6=%9d\n", c[0], cr[0]=c[0]/12, c[4], cr[4]=c[4]/6);
if(cr[0]*12!=c[0])puts("c1 division error");if(cr[4]*6!=c[4])puts("C1 division error");
printf("c3 %9d/4 =%9d C3 %9d/2=%9d\n", c[1], cr[1]=c[1]/4, c[5], cr[5]=c[5]/2);
if(cr[1]*4!=c[1])puts("c3 division error");if(cr[5]*2!=c[5])puts("C3 division error");
printf("cs %9d/6 =%9d CS %9d/3=%9d\n", c[2], cr[2]=c[2]/6, c[6], cr[6]=c[6]/3);
if(cr[2]*6!=c[2])puts("cs division error");if(cr[6]*3!=c[6])puts("CS division error");
printf("c3v %9d/2 =%9d C3V %9d/1=%9d\n", c[3], cr[3]=c[3]/2, c[7], cr[7]=c[7]);
if(cr[3]*2!=c[3])puts("c3v division error");
for(int i=8;i--;)cr[8]+=cr[i];
printf("total =%d unique =%d",c[8],cr[8]);
}
Wynik
Program generuje tabelę wyników 8 wpisów, zgodnie z 8 symetriami bryły. Bryła może mieć dowolną z 4 następujących symetrii (notacja Schoenfliesa)
c1: no symmetry
c3: 3-fold axis of rotation (produces 3-fold axis of rotation in hexagon tiling)
cs: plane of reflection (produces line of reflection in hexagon tiling)
c3v both of the above (produces 3-fold axis of rotation and three lines of reflection through the hexagon corners)
Dodatkowo, gdy bryła ma dokładnie połowę komórek z jedynkami i połowę z zerami, istnieje możliwość odwrócenia wszystkich jedynek i zer, a następnie odwrócenia współrzędnych przez środek przestrzeni sześcianu. To właśnie nazywam samouzupełnianiem, ale bardziej matematyczny termin byłby „antysymetryczny w stosunku do centrum inwersji”.
Ta operacja symetrii daje 2-krotną oś obrotu w kafelku sześciokąta.
Wzory o tej symetrii są wymienione w osobnej kolumnie. Występują tylko tam, gdzie N jest parzyste.
Moje obliczenie wydaje się być nieco wyłączone dla N = 4. W dyskusji z Peterem Taylorem wydaje się, że nie wykrywam przechyłek, które mają jedynie symetrię linii przechodzącej przez krawędzie sześciokąta. Jest tak prawdopodobnie dlatego, że nie testowałem samokompletu (antysymetrii) dla operacji innych niż (inwersja) x (tożsamość). Testowanie samokompletu dla operacji (inwersja) x (odbicie) i (inwersja) x (3-krotny obrót ) może odkryć brakujące symetrie. Spodziewałbym się wtedy, że pierwsza linia danych dla N = 4 będzie wyglądać tak (16 mniej w C1 i 32 więcej w C1):
c1 224064/12=18672 C1 534/6=89
Dzięki temu sumy będą zgodne z odpowiedzią Petera i https://oeis.org/A066931/a066931.txt
prąd wyjściowy jest następujący.
N=1
non self-complement self-complement
c1 0/12= 0 C1 0/6= 0
c3 0/4 = 0 C3 0/2= 0
cs 0/6 = 0 CS 0/3= 0
c3v 2/2 = 1 C3V 0/1= 0
total =2 unique =1
non self-complement self-complement
N=2
c1 0/12= 0 C1 0/6= 0
c3 0/4 = 0 C3 0/2= 0
cs 12/6 = 2 CS 3/3= 1
c3v 4/2 = 2 C3V 1/1= 1
total =20 unique =6
N=3
non self-complement self-complement
c1 672/12=56 C1 0/6= 0
c3 4/4 = 1 C3 0/2= 0
cs 288/6 =48 CS 0/3= 0
c3v 16/2 = 8 C3V 0/1= 0
total =980 unique =113
N=4 (errors as discussed)
non self-complement self-complement
c1 224256/12=18688 C1 342/6=57
c3 64/4 =16 C3 2/2= 1
cs 8064/6 =1344 CS 54/3=18
c3v 64/2 =32 C3V 2/1= 2
total =232848 unique =20158
N=5
non self-complement self-complement
c1 266774112/12=22231176 C1 0/6= 0
c3 1100/4 =275 C3 0/2= 0
cs 451968/6 =75328 CS 0/3= 0
c3v 352/2 =176 C3V 0/1= 0
total =267227532 unique =22306955
Lista spraw (zaktualizowana)
Uporządkuj bieżący kod.
Zrobione mniej więcej
Zaimplementuj sprawdzanie symetrii dla bieżącej warstwy i przekaż parametr dla symetrii poprzedniej warstwy (nie ma sensu sprawdzać, czy ostatnia warstwa była asymetryczna).
Gotowe, wyniki dla nieparzystego N zgadzają się z opublikowanymi danymi
Dodaj opcję, aby ukryć liczenie liczb asymetrycznych (powinno działać znacznie szybciej)
Można to zrobić, dodając kolejny warunek do wywołania rekurencji: if(s1 && m<n*3-2)f(m + 1,e+d,s1)Skraca czas działania dla N = 5 z 5 minut do około sekundy. W rezultacie pierwszy wiersz wyniku staje się całkowitym śmieciem (podobnie jak sumy całkowite), ale jeśli suma jest już znana z OEIS, liczbę asymetrycznych przechyleń można odtworzyć, przynajmniej dla nieparzystej N.
Ale nawet dla N liczba asymetrycznych (zgodnie z symetriami c3v) ciał stałych, które są samouzupełnianiem, zostałaby utracona. W tym przypadku przydatny może być osobny program dedykowany ciałom stałym z dokładnie (N ** 3) / 2 komórkami z 1. Przy tym dostępnym (i liczącym poprawnie) wypróbowanie N = 6 może być możliwe, ale uruchomienie zajmie dużo czasu.
Zaimplementuj zliczanie komórek, aby zredukować wyszukiwanie do (N ^ 3) / 2 kostek.
Nie zrobione, oczekiwane oszczędności będą marginalne
Zaimplementuj sprawdzanie symetrii (komplementarne bryły) dla wzorów zawierających dokładnie (N ^ 3) / 2 kostki.
Zrobione, ale wydaje się, że występują pominięcia, patrz N = 4.
Znajdź sposób na wybranie najniższej leksykalnie liczby z asymetrycznej.
Oczekuje się, że oszczędności nie będą tak duże. Tłumienie asymetrycznych liczb eliminuje większość tego. Jedynym sprawdzanym odbiciem jest płaszczyzna przechodząca przez oś y (xiz obliczane są później przez pomnożenie przez 3). Liczby z tylko symetrią obrotową są liczone w obu postaciach enancjomerycznych. Być może działałby prawie dwa razy szybciej, gdyby tylko jeden został policzony.
Aby to ułatwić, prawdopodobnie popraw sposób wyświetlania współrzędnych w każdej warstwie (tworzą one zdegenerowane grupy 6 lub 3, ewentualnie z grupą 1 w dokładnym środku warstwy).
Ciekawe, ale prawdopodobnie na stronie są inne pytania do zbadania.
N = 6daje wynik większy niż 10 ^ 12, niekonstruktywne rozwiązanie jest prawie na pewno konieczne, aby dojść tak daleko.