OEIS erweitern: Diamond Tilings zählen

46

Ich verspreche, dies wird meine letzte Herausforderung in Bezug auf Diamantkacheln sein (zumindest für eine Weile). Positiv zu vermerken ist, dass diese Herausforderung nichts mit ASCII-Kunst zu tun hat und auch kein Code-Golf ist.

Zur Erinnerung, jedes Sechseck kann mit drei verschiedenen Diamanten versehen werden:

Eine interessante Frage ist, wie viele dieser Kacheln für eine bestimmte Sechseckgröße existieren. Es scheint, dass diese Zahlen ziemlich gründlich untersucht wurden und in OEIS A008793 zu finden sind .

Das Problem wird jedoch schwieriger, wenn wir uns fragen, wie viele Kacheln bis zur Drehung und Reflexion vorhanden sind . Beispielsweise existieren für die Seitenlänge N = 2 die folgenden 20 Kacheln:

   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\/_/\_\ /\_\/\_\ /\_\/_/\ /\/_/_/\ /\_\/\_\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/_/\/_/ \/\_\/_/ \/\_\_\/ \/_/\_\/ \/_/\/_/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \_\/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/   \_\/_/   \_\/_/ 
   ____     ____     ____     ____     ____     ____     ____     ____     ____     ____  
  /_/_/\   /\_\_\   /_/\_\   /_/_/\   /_/\_\   /_/\_\   /_/_/\   /_/_/\   /_/_/\   /_/_/\ 
 /\_\_\/\ /\/_/_/\ /_/\/_/\ /\_\_\/\ /\_\/_/\ /_/\/_/\ /_/\_\/\ /\_\_\/\ /_/\_\/\ /_/_/\/\
 \/\_\_\/ \/_/_/\/ \_\/\_\/ \/_/\_\/ \/_/_/\/ \_\/_/\/ \_\/\_\/ \/_/_/\/ \_\/_/\/ \_\_\/\/
  \/_/_/   \_\_\/   \_\/_/   \_\/_/   \_\_\/   \_\_\/   \_\/_/   \_\_\/   \_\_\/   \_\_\/ 

Viele davon sind jedoch in Bezug auf Rotation und Reflexion identisch. Wenn wir diese Symmetrien berücksichtigen, bleiben nur 6 verschiedene Kacheln übrig:

   ____     ____     ____     ____     ____     ____  
  /\_\_\   /\_\_\   /\_\_\   /_/\_\   /_/\_\   /_/\_\ 
 /\/\_\_\ /\/_/\_\ /\/_/_/\ /\_\/_/\ /\_\/_/\ /_/\/\_\
 \/\/_/_/ \/\_\/_/ \/\_\_\/ \/\_\_\/ \/_/\_\/ \_\/\/_/
  \/_/_/   \/_/_/   \/_/_/   \/_/_/   \_\/_/   \_\/_/ 

   2        2        6        6        1        3

Dabei geben die Zahlen die Vielzahl der Kacheln an. Beachten Sie, dass es für größere Sechsecke auch Fliesen mit den Multiplikationen 4 und 12 gibt.

Es scheint, dass die Anzahl der Kacheln bis zur Symmetrie weniger gründlich untersucht wurde. Der OEIS-Eintrag A066931 listet nur die fünf Begriffe auf:

1, 1, 6, 113, 20174

wobei der erste Term für die Seitenlänge N = 0und der letzte Term für die Seitenlänge steht N = 4.

Ich bin sicher, wir können es besser machen!

Ihre Aufgabe ist es, die Anzahl der Kacheln für eine bestimmte Seitenlänge zu berechnen.

Dies ist der . Ihre Punktzahl ist die höchste Seitenlänge, Nfür die Ihr Code innerhalb von 30 Minuten auf meinem Computer das richtige Ergebnis liefert . Im Falle eines Unentschieden akzeptiere ich die Einsendung, die das Ergebnis für das N schnellste ergibt .

Wie üblich dürfen Sie keine bereits bekannten Ergebnisse fest codieren, um den Tie-Breaker zu gewinnen. Der zu lösende Algorithmus N = 3sollte mit dem zu lösenden identisch sein N = 5.

Ihr Beitrag darf nicht mehr als 4 GB Arbeitsspeicher belegen. Ich werde etwas Spielraum geben, wenn Sie nahe an diesem Limit operieren, aber wenn Sie durchweg über diesem Limit sind oder wenn Sie deutlich darüber hinausgehen, werde ich das Nfür Ihre Einreichung nicht berücksichtigen.

Ich werde alle Einsendungen auf meinem Windows 8-Computer testen. Stellen Sie daher sicher, dass Ihre bevorzugte Sprache unter Windows frei verfügbar ist. Die einzige Ausnahme ist Mathematica (weil ich eine Lizenz dafür habe). Bitte fügen Sie Anweisungen zum Kompilieren / Ausführen Ihres Codes bei.

Natürlich können Sie in Ihrer Freizeit mehr Begriffe berechnen (für die Wissenschaft und für andere, um ihre Zahlen zu überprüfen), aber die Punktzahl Ihrer Antwort wird in diesen 30 Minuten ermittelt.

Martin Ender
quelle
4
Beachten Sie, dass bei N = 6einer Ausgabe von mehr als 10 ^ 12 mit ziemlicher Sicherheit eine nicht konstruktive Lösung erforderlich ist, um dieses Ziel zu erreichen.
Peter Taylor
1
@PeterTaylor Ich hatte gehofft, dass es mehr Raum für Verbesserungen gibt. Vielleicht ein paar einfache konstruktive Antworten, die N = 5 ergeben, um mehr Einsicht in das Problem zu gewinnen, und dann potenziell hybride Ansätze, die nicht alle Kacheln konstruieren müssen, sondern die Gesamtzahl aus ein paar konstruierten extrapolieren können ... und dann vielleicht etwas Analytisches, wenn wir wirklich Glück haben. :)
Martin Ender
2
Auf die Gefahr hin, das Offensichtliche auszudrücken, scheint mir jede dieser Kacheln einer Projektion einer Zusammenstellung von Einheitswürfeln aus einer entfernten Perspektive zu entsprechen, z. B. von (100, -100, 100). Ich finde, dass dies die Last des Baus von Fliesen erleichtert.
DavidC
1
@ DavidCarraher In der Tat. Insbesondere ist eine solche Anordnung von Einheitswürfeln ein 3D- Young-Diagramm . (Vielleicht hilft das jemandem.)
Martin Ender
@DavidCarraher Wenn Sie das große Sechseck genau genug betrachten, können Sie es auf zwei verschiedene Arten als junges Diagramm interpretieren. Der naheliegende Weg (zumindest für mich) ist, einen flachen Bereich oben links zu sehen, in dessen oberer linken Ecke ein 2x2x1-Quader fehlt. Aber es gibt eine andere Sichtweise: eine leere Zone in diesem Bereich, in der ein 2x2x1-Quader sitzt. Das Kippen um 60 Grad kann helfen. Es tut mir in den Augen weh, aber ich denke, die beiden jungen Diagramme passen zusammen, möglicherweise durch die Reflexion eines von ihnen. OEIS A008793 ist sehr vorsichtig mit seinem Wortlaut: "Anzahl der ebenen Partitionen, deren junge Diagramme ..."
Level River St

Antworten:

80

Algebra, Graphentheorie, Möbius-Inversion, Forschung und Java

Die Symmetriegruppe des Sechsecks ist die Diedergruppe der Ordnung 12 und wird durch eine Drehung um 60 Grad und einen Spiegelschlag über einen Durchmesser erzeugt. Es hat 16 Untergruppen, aber einige von ihnen sind in nicht-trivialen Konjugationsgruppen (diejenigen, die nur Reflexionen haben, haben 3 Wahlmöglichkeiten der Achse), so dass es 10 grundlegend verschiedene Symmetrien gibt, die eine Kachelung des Sechsecks haben kann:

Bilder der 10 Symmetrien

Die Anzahl der Diamantkacheln einer Teilmenge eines Dreiecksgitters kann als Determinante berechnet werden. Mein ursprünglicher Ansatz bestand darin, für jede der Symmetrien des Sechsecks eine Determinante zu erstellen, um die Anzahl der Kacheln zu berechnen, die mindestens diese Symmetrien aufweisen ; und verwenden Sie dann die Möbius-Inversion in der Inzidenzalgebra ihres Posets (im Grunde genommen eine Verallgemeinerung des Einschluss-Ausschluss-Prinzips), um die Anzahl der Kacheln zu berechnen, deren Symmetriegruppe genau jeder der 10 Fälle ist. Einige der Symmetrien haben jedoch schlechte Randbedingungen, so dass ich gezwungen war, über exponentiell viele Determinanten zu summieren. Zum Glück sind die Werte für erhaltenn < 10gab mir genug Daten, um relevante Sequenzen in OEIS zu identifizieren und eine geschlossene Form zusammenzusetzen (für einen Wert von "closed", der endliche Produkte erlaubt). In der formalen Beschreibung, die ich vorbereitet habe, um die OEIS-Sequenzaktualisierungen zu rechtfertigen, werden die Sequenzen ein wenig besprochen und auf Beweise verwiesen .

Sobald die Doppelzählung erledigt ist, stellt sich heraus, dass sich vier der zehn Werte ordentlich aufheben, sodass wir nur die verbleibenden sechs berechnen und dann eine gewichtete Summe erstellen müssen.

Dieser Code dauert N=1000auf meinem Computer weniger als 30 Sekunden .

import java.math.BigInteger;

public class OptimisedCounter {
    private static int[] minp = new int[2];

    public static void main(String[] args) {
        if (args.length > 0) {
            for (String arg : args) System.out.println(count(Integer.parseInt(arg)));
        }
        else {
            for (int n = 0; n < 16; n++) {
                System.out.format("%d\t%s\n", n, count(n));
            }
        }
    }

    private static BigInteger count(int n) {
        if (n == 0) return BigInteger.ONE;

        if (minp.length < 3*n) {
            int[] wider = new int[3*n];
            System.arraycopy(minp, 0, wider, 0, minp.length);
            for (int x = minp.length; x < wider.length; x++) {
                // Find the smallest prime which divides x
                for (wider[x] = 2; x % wider[x] != 0; wider[x]++) { /* Do nothing */ }
            }
            minp = wider;
        }

        BigInteger E = countE(n), R2 = countR2(n), F = countF(n), R3 = countR3(n), R = countR(n), FR = countFR(n);
        BigInteger sum = E.add(R3);
        sum = sum.add(R2.add(R).multiply(BigInteger.valueOf(2)));
        sum = sum.add(F.add(FR).multiply(BigInteger.valueOf(3)));
        return sum.divide(BigInteger.valueOf(12));
    }

    private static BigInteger countE(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR2(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            w[3*i+2]++;
            for (int j = 3*i + 1; j <= 2*i + n + 1; j++) w[j]--;
            for (int j = 2*i + n + 1; j <= i + n + n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countF(int n) {
        int[] w = new int[3*n];
        for (int i = 0; i < n; i++) {
            for (int j = 2*i + 1; j <= 2*i + n; j++) w[j]--;
            for (int j = i + n + 1; j <= i + 2*n; j++) w[j]++;
        }
        return powerProd(w);
    }

    private static BigInteger countR3(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        return countE(n / 2).pow(2);
    }

    private static BigInteger countR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*m-1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= 3*i+1; j++) w[j] += 2;
            for (int j = 1; j <= i + m; j++) w[j] -= 2;
        }
        return powerProd(w);
    }

    private static BigInteger countFR(int n) {
        if ((n & 1) == 1) return BigInteger.ZERO;
        int m = n / 2;
        int[] w = new int[3*n-2];
        for (int j = 1; j <= m; j++) w[j]--;
        for (int j = 2*m; j <= 3*m-1; j++) w[j]++;
        for (int i = 0; i <= 2*m-3; i++) {
            for (int j = i + 2*m + 1; j <= i + 4*m; j++) w[j]++;
            for (int j = 2*i + 3; j <= 2*i + 2*m + 2; j++) w[j]--;
        }
        return powerProd(w);
    }

    private static BigInteger powerProd(int[] w) {
        BigInteger result = BigInteger.ONE;
        for (int x = w.length - 1; x > 1; x--) {
            if (w[x] == 0) continue;

            int p = minp[x];
            if (p == x) result = result.multiply(BigInteger.valueOf(p).pow(w[p]));
            else {
                // Redistribute it. This should ensure we avoid negatives.
                w[p] += w[x];
                w[x / p] += w[x];
            }
        }

        return result;
    }
}
Peter Taylor
quelle
24
Du bist wirklich ein Gott unter den Sterblichen. Ich hoffe, dass Ihre Lösung in einem renommierten Journal veröffentlicht wird.
Alex A.
Das ist fantastisch. BTW mein (derzeit nicht veröffentlichter) Code gibt 22306956 für N = 5: 22231176 (12) +275 (4) +75328 (6) +352 (2), eine Diskrepanz von 1, die ungerade ist. Ich habe keine Ahnung, dass Sie hier sind. Ist es für eine Aufschlüsselung nach Symmetrien geeignet? Für N = 4 bin ich 16 niedriger als du und oeis.org/A066931/a066931.txt Aus dieser Referenz geht hervor, dass ich 16 zu viele der Multiplizität 12 habe, die ich in 32 der Multiplizität 6 umwandeln muss zu überrascht, auch N sind schwieriger für mich. Aber ich habe keine Probleme mit ungeraden N und bekomme die richtigen Antworten für 0 <N <4. Sucht nach offensichtlichen Problemen und postet morgen meinen Code.
Level River St
@steveverrill, wenn ich die Notation verstehe, für N = 5 mache ich es 22231176 (12) + 75328 (6) + 275 (4) + 176 (2). Ich denke, Sie können den Index 2 nicht durch 2 teilen. (FWIW für ungerade Zahlen haben alle eine Symmetrieachse, die durch zwei Eckpunkte und eine Rotationssymmetrie der Ordnung 3 verläuft.)
Peter Taylor
@steveverrill, und für N = 4 scheint Ihre Diskrepanz perfekt für die Zahl zu sein, deren Symmetrieachse durch die Mittelpunkt zweier Kanten verläuft.
Peter Taylor
3
Beeindruckend, dass Sie das gelöst haben. Ich hoffe, dass Sie irgendwann eine Antwort veröffentlichen, der auch Nicht-Mathematiker folgen können.
DavidC
15

C

Einführung

Wie David Carraher bemerkte, schien die einfachste Möglichkeit, die Sechseckkacheln zu analysieren, darin zu bestehen, ihren Isomorphismus mit dem dreidimensionalen jungen Diagramm auszunutzen, das im Wesentlichen ein XY-Quadrat ist, das mit ganzzahligen Höhenbalken gefüllt ist, deren Z-Höhen gleich bleiben oder zunehmen müssen wenn die z-Achse angefahren wird.

Ich habe mit einem Algorithmus zum Ermitteln der Summen begonnen, der sich besser für die Symmetriezählung eignet als der veröffentlichte Algorithmus, der auf einer Abweichung von einer der drei kartesischen Achsen basiert.

Algorithmus

Ich beginne damit, die Zellen der x-, y- und z-Ebene mit Einsen zu füllen, während der Rest des Bereichs Nullen enthält. Sobald dies erledigt ist, baue ich das Muster Schicht für Schicht auf, wobei jede Schicht die Zellen enthält, die einen gemeinsamen 3D-Manhattan-Abstand vom Ursprung haben. Eine Zelle kann nur eine 1 enthalten, wenn die drei darunter liegenden Zellen auch eine 1 enthalten. Wenn eine davon eine 0 enthält, muss die Zelle eine 0 sein.

Der Vorteil des Aufbaus des Musters auf diese Weise besteht darin, dass jede Schicht symmetrisch zur x = y = z-Linie ist. Dies bedeutet, dass jede Schicht unabhängig auf Symmetrie überprüft werden kann.

Symmetrieprüfung

Die Symmetrien des Festkörpers sind wie folgt: Dreifache Drehung um die x = y = z-Linie -> Dreifache Drehung um das Sechseckzentrum; und 3 x Reflexionen über die 3 Ebenen, die die Linie x = y = z enthalten, und jede der Achsen x, y, z -> Reflexion über die Linien durch die Sechseckecken.

Dies ergibt nur eine 6-fache Symmetrie. Um die volle Symmetrie des Sechsecks zu erhalten, muss eine andere Art von Symmetrie berücksichtigt werden. Jeder Körper (aufgebaut aus Einsen) hat einen komplementären Körper (aufgebaut aus Nullen). Wenn N ungerade ist, muss sich der komplementäre Festkörper vom ursprünglichen Festkörper unterscheiden (da nicht die gleiche Anzahl von Würfeln möglich ist). Wenn der komplementäre Volumenkörper jedoch gedreht wird, wird festgestellt, dass seine 2D-Darstellung als Diamantkachel (mit Ausnahme einer zweifachen Symmetrieoperation) mit dem ursprünglichen Volumenkörper identisch ist. Wenn N gerade ist, ist es möglich, dass der Festkörper selbstinvers ist.

Dies geht aus den Beispielen für N = 2 in der Frage hervor. Von links betrachtet sieht das erste Sechseck wie ein fester Würfel mit 8 kleinen Würfeln aus, während das letzte Sechseck wie eine leere Hülle mit 0 kleinen Würfeln aussieht. Von rechts gesehen ist das Gegenteil der Fall. Das 3., 4. und 5. Sechseck sowie das 16., 17. und 18. Sechseck scheinen entweder 2 oder 6 Würfel zu enthalten und ergänzen sich daher in 3 Dimensionen. Sie sind in 2 Dimensionen durch eine 2-fache Symmetrieoperation (2-fache Drehung oder Reflexion um eine Achse durch die Sechskantkanten) miteinander verbunden. Andererseits zeigen das 9., 10., 11. und 12. Sechseck 3D-Muster, die sind ihre eigenen Komplemente und haben daher eine höhere Symmetrie (dies sind daher die einzigen Muster mit ungerader Multiplizität).

Es ist zu beachten, dass (N ^ 3) / 2 Würfel eine notwendige Bedingung sind, um sich selbst zu ergänzen, aber im Allgemeinen ist es keine ausreichende Bedingung, wenn N> 2 ist. All dies hat zur Folge, dass bei ungeraden N die Kacheln immer paarweise auftreten (N ^ 3) / 2 Würfel müssen sorgfältig geprüft werden.

Aktueller Code (generiert die richtige Summe für N = 1,2,3,5. Fehler wie für N = 4 beschrieben.)

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]);    
}

Ausgabe

Das Programm generiert eine Ausgabetabelle mit 8 Einträgen entsprechend den 8 Symmetrien des Volumenkörpers. Der Körper kann eine der folgenden 4 Symmetrien haben (Schönflies-Notation)

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)

Wenn der Körper genau die Hälfte der Zellen mit Einsen und die Hälfte mit Nullen hat, besteht außerdem die Möglichkeit, alle Einsen und Nullen zu spiegeln und dann die Koordinaten durch die Mitte des Würfelraums zu invertieren. Das nenne ich Selbstkomplement, aber ein mathematischerer Begriff wäre "antisymmetrisch in Bezug auf ein Inversionszentrum".

Diese Symmetrieoperation ergibt eine zweifache Rotationsachse in der Sechskantfliese.

Muster mit dieser Symmetrie werden in einer separaten Spalte aufgelistet. Sie treten nur dort auf, wo N gerade ist.

Meine Zählung scheint für N = 4 leicht abzulaufen. In der Diskussion mit Peter Taylor scheint es, als würde ich keine Fliesen erkennen, die nur eine Symmetrie einer Linie durch die Sechskantkanten haben. Dies liegt vermutlich daran, dass ich nicht auf Selbstkomplement (Antisymmetrie) für andere Operationen als (Inversion) x (Identität) getestet habe ) kann die fehlenden Symmetrien aufdecken. Ich würde dann erwarten, dass die erste Zeile der Daten für N = 4 so aussieht (16 weniger in c1 und 32 mehr in C1):

c1   224064/12=18672          C1  534/6=89

Dies würde die Gesamtsummen mit Peters Antwort und https://oeis.org/A066931/a066931.txt in Einklang bringen

Stromausgang ist wie folgt.

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

Aufgabenliste (aktualisiert)

Aktuellen Code aufräumen.

Fertig, mehr oder weniger

Implementieren Sie die Symmetrieprüfung für die aktuelle Ebene und übergeben Sie einen Parameter für die Symmetrie der vorherigen Ebene (es ist nicht sinnvoll zu prüfen, ob die letzte Ebene asymmetrisch war).

Fertig, Ergebnisse für ungerade N stimmen mit veröffentlichten Daten überein

Hinzufügen einer Option zum Unterdrücken des Zählens asymmetrischer Zahlen (sollte viel schneller laufen)

Dies kann erreicht werden, indem dem Rekursionsaufruf eine weitere Bedingung hinzugefügt wird: if(s1 && m<n*3-2)f(m + 1,e+d,s1)Die Laufzeit für N = 5 wird von 5 Minuten auf etwa eine Sekunde verringert. Infolgedessen wird die erste Zeile der Ausgabe zu Gesamtmüll (wie auch die Gesamtsummen), aber wenn die Gesamtsumme bereits aus OEIS bekannt ist, kann die Anzahl der asymmetrischen Kacheln zumindest für ungerade N wiederhergestellt werden.

Aber für gerade N würde die Anzahl der asymmetrischen (gemäß c3v-Symmetrien) Festkörper, die sich selbst ergänzen, verloren gehen. In diesem Fall kann ein separates Programm für Volumenkörper mit genau (N ** 3) / 2 Zellen mit einer 1 nützlich sein. Wenn dies verfügbar ist (und korrekt gezählt wird), kann möglicherweise N = 6 ausprobiert werden, die Ausführung dauert jedoch sehr lange.

Implementieren Sie das Zählen von Zellen, um die Suche auf bis zu (N ^ 3) / 2 Würfel zu reduzieren.

Nicht erledigt, Einsparungen werden marginal erwartet

Implementieren Sie die Symmetrieprüfung (komplementärer Körper) für Muster, die genau (N ^ 3) / 2 Würfel enthalten.

Fertig, scheint aber Auslassungen zu haben, siehe N = 4.

Finden Sie einen Weg, die lexikalisch niedrigste Zahl aus einer asymmetrischen Zahl zu wählen.

Es wird nicht erwartet, dass die Einsparungen so groß sind. Das Unterdrücken von asymmetrischen Figuren beseitigt das meiste davon. Die einzige überprüfte Reflexion ist die Ebene durch die y-Achse (x und z werden später durch Multiplikation mit 3 berechnet.) Figuren mit nur Rotationssymmetrie werden in ihren beiden enantiomeren Formen gezählt. Vielleicht würde es fast doppelt so schnell laufen, wenn nur einer gezählt würde.

Um dies zu vereinfachen, verbessern Sie möglicherweise die Art und Weise, wie die Koordinaten in jeder Ebene aufgelistet werden (sie bilden entartete Gruppen von 6 oder 3, wobei sich möglicherweise eine Gruppe von 1 genau in der Mitte der Ebene befindet).

Interessant, aber wahrscheinlich gibt es noch andere Fragen auf der Website zu erkunden.

Level River St
quelle