Memperluas OEIS: Menghitung Memiringkan Berlian

46

Saya berjanji, ini akan menjadi tantangan terakhir saya tentang diamong tilings (untuk sementara waktu). Sisi baiknya, tantangan ini tidak ada hubungannya dengan seni ASCII, dan juga bukan golf kode, jadi ini sebenarnya sangat berbeda.

Jadi sebagai pengingat, setiap segi enam dapat diberi judul dengan tiga berlian berbeda:

Sebuah pertanyaan yang menarik untuk ditanyakan adalah berapa banyak tilings ini ada untuk ukuran segi enam yang diberikan. Tampaknya angka-angka ini telah dipelajari dengan cukup teliti dan dapat ditemukan di OEIS A008793 .

Namun, masalahnya menjadi lebih rumit jika kita bertanya berapa banyak tilings yang ada hingga rotasi dan refleksi . Misalnya, untuk panjang sisi N = 2, 20 tilings berikut ada:

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

Tetapi banyak dari ini identik di bawah rotasi dan refleksi. Jika kita memperhitungkan simetri ini, hanya tersisa 6 til yang berbeda:

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

   2        2        6        6        1        3

di mana angka-angka menunjukkan banyaknya setiap ubin. Perhatikan bahwa untuk hexagon yang lebih besar ada juga tilings dengan multiplisitas 4 dan 12.

Tampaknya jumlah kemiringan hingga simetri telah dipelajari kurang teliti. Entri OEIS A066931 hanya mencantumkan lima istilah:

1, 1, 6, 113, 20174

di mana istilah pertama adalah untuk panjang sisi N = 0dan istilah terakhir untuk panjang sisi N = 4.

Saya yakin kita bisa melakukan lebih baik dari itu!

Tugas Anda adalah menghitung jumlah kemiringan untuk panjang sisi tertentu.

Ini adalah . Skor Anda akan menjadi sisi-panjang tertinggi Nyang kode Anda menghasilkan hasil yang benar dalam waktu 30 menit pada mesin saya. Dalam hal seri, saya akan menerima kiriman yang menghasilkan hasil untuk yang N tercepat.

Seperti biasa, Anda tidak boleh hasil hardcode yang sudah Anda tahu untuk memenangkan tie-breaker. Algoritma yang memecahkan N = 3harus identik dengan yang memecahkan N = 5.

Kiriman Anda tidak boleh menggunakan memori lebih dari 4GB. Saya akan memberikan beberapa kelonggaran pada hal ini jika Anda beroperasi mendekati batas itu, tetapi jika Anda secara konsisten di atas batas itu, atau jika Anda melonjak secara signifikan di luar batas itu, saya tidak akan menghitungnya Nuntuk pengiriman Anda.

Saya akan menguji semua pengiriman pada mesin Windows 8 saya, jadi pastikan bahasa pilihan Anda tersedia secara bebas di Windows. Satu-satunya pengecualian untuk ini adalah Mathematica (karena saya kebetulan memiliki lisensi untuk itu). Harap sertakan instruksi untuk mengkompilasi / menjalankan kode Anda

Tentu saja, merasa bebas untuk menghitung lebih banyak istilah dalam waktu Anda sendiri (untuk sains, dan bagi orang lain untuk memeriksa angka-angka mereka), tetapi skor jawaban Anda akan ditentukan dalam 30 menit tersebut.

Martin Ender
sumber
4
Perhatikan bahwa karena N = 6memberikan output lebih dari 10 ^ 12, solusi non-konstruktif hampir pasti diperlukan untuk mencapai sejauh itu.
Peter Taylor
1
@PeterTaylor Saya berharap itu akan memberikan lebih banyak ruang untuk perbaikan. Mungkin beberapa jawaban konstruktif sederhana pertama yang dapat melakukan N = 5 untuk mendapatkan lebih banyak wawasan tentang masalah, dan kemudian berpotensi pendekatan hybrid yang tidak perlu membangun semua tilings tetapi dapat memperkirakan jumlah total dari beberapa yang dibangun ... dan mungkin sesuatu yang analitik jika kita benar-benar beruntung. :)
Martin Ender
2
Dengan risiko menyatakan yang jelas, bagi saya tampaknya setiap ubin tersebut sesuai dengan proyeksi kumpulan unit kubus yang dilihat dari sudut pandang yang jauh, misalnya dari (100, -100.100). Saya menemukan bahwa ini meringankan beban membangun miring.
DavidC
1
@DavidCarraher Memang. Lebih khusus, susunan kubus satuan seperti itu adalah diagram 3D Young . (Mungkin itu membantu seseorang.)
Martin Ender
@ Davidvider Jika Anda melihat cukup keras pada segi enam besar, Anda akan melihat ada 2 cara berbeda untuk menafsirkannya sebagai diagram muda. Cara yang jelas (setidaknya untuk saya) adalah melihat area datar di bagian atas dan kiri dengan kubus 2x2x1 hilang dari sudut kiri atas. Tapi ada cara lain untuk melihatnya: zona kosong di daerah itu, dengan 2x2x1 kuboid duduk di dalamnya. Memiringkan 60 derajat dapat membantu. Itu menyakitkan mata saya, tetapi saya pikir dua diagram muda cocok bersama, mungkin dengan refleksi dari salah satunya. OEIS A008793 sangat berhati-hati dengan kata-katanya: "jumlah partisi pesawat yang diagram mudanya ..."
Level River St

Jawaban:

80

Aljabar, teori grafik, inversi Möbius, penelitian, dan Jawa

Gugus simetri hexagon adalah kelompok dihedral orde 12, dan dihasilkan oleh rotasi 60 derajat dan cermin membalik diameter. Ini memiliki 16 subkelompok, tetapi beberapa dari mereka berada dalam kelompok konjugasi non-sepele (yang hanya memiliki refleksi memiliki 3 pilihan sumbu), jadi ada 10 simetri yang berbeda secara mendasar yang dapat dimiliki oleh sebuah ubin segi enam:

Gambar 10 simetri

Jumlah kemiringan intan dari subset kisi segitiga dapat dihitung sebagai penentu , jadi pendekatan awal saya adalah menyiapkan satu determinan untuk masing-masing simetri segi enam, untuk menghitung jumlah kemiringan yang memiliki setidaknya simetri tersebut. ; dan kemudian menggunakan inversi Mbius dalam aljabar kejadian poset mereka (pada dasarnya generalisasi dari prinsip inklusi-eksklusi) untuk menghitung jumlah tilings yang kelompok simetrinya persis masing-masing dari 10 kasus. Namun, beberapa simetri memiliki kondisi tepi yang buruk, jadi saya terpaksa menjumlahkan banyak faktor penentu secara eksponensial. Untungnya, nilai yang didapatn < 10memberi saya cukup data untuk dapat mengidentifikasi urutan yang relevan dalam OEIS dan mengumpulkan bentuk tertutup (untuk beberapa nilai "ditutup" yang memungkinkan produk hingga). Ada sedikit diskusi tentang urutan, dan referensi untuk bukti, dalam penulisan resmi yang saya siapkan untuk membenarkan pembaruan urutan OEIS.

Setelah penghitungan ganda diatasi, ternyata empat dari sepuluh nilai dibatalkan dengan rapi, jadi kita hanya perlu menghitung enam sisanya dan kemudian melakukan penjumlahan berbobot.

Kode ini membutuhkan waktu kurang dari 30 detik untuk N=1000komputer saya.

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
sumber
24
Anda benar-benar dewa di antara manusia. Saya berharap solusi Anda dipublikasikan di jurnal bergengsi.
Alex A.
Ini luar biasa. BTW kode saya (saat ini tidak diposting) memberikan 22306956 untuk N = 5: 22231176 (12) +275 (4) +75328 (6) +352 (2), perbedaan 1, yang aneh. Saya tidak tahu apa yang Anda lakukan di sini, apakah itu cocok untuk gangguan simetri? Untuk N = 4 saya 16 lebih rendah dari Anda dan oeis.org/A066931/a066931.txt Dari referensi itu tampaknya saya memiliki 16 terlalu banyak multiplisitas 12, yang saya perlu ubah ke 32 dari multiplisitas 6. Saya tidak terlalu terkejut, bahkan N lebih sulit bagiku. Tapi saya tidak punya masalah dengan N aneh dan saya mendapatkan jawaban yang benar untuk 0 <N <4. Akan mencari masalah yang jelas dan memposting kode saya besok.
Level River St
@steveverrill, jika saya mengerti notasi, untuk N = 5 saya membuatnya 22231176 (12) + 75328 (6) + 275 (4) + 176 (2). Saya pikir Anda gagal untuk membagi indeks 2 dengan 2. (FWIW untuk bilangan ganjil mereka semua memiliki sumbu simetri melewati dua simpul dan simetri rotasi urutan 3).
Peter Taylor
@steveverrill, dan untuk N = 4 perbedaan Anda tampaknya sangat cocok untuk angka yang memiliki sumbu simetri yang melewati titik tengah dua sisi.
Peter Taylor
3
Mengesankan bahwa Anda memecahkan ini. Saya berharap Anda akhirnya akan mengirim jawaban yang bisa diikuti oleh non-ahli matematika.
DavidC
15

C

pengantar

Seperti dikomentari oleh David Carraher, cara paling sederhana menganalisis ubin segi enam tampaknya mengambil keuntungan dari isomorfisma dengan Diagram Young 3 dimensi, pada dasarnya x, y persegi diisi dengan bar tinggi bilangan bulat yang z ketinggiannya harus tetap sama atau meningkat sebagai sumbu z didekati.

Saya mulai dengan sebuah algoritma untuk menemukan total yang lebih dapat diterima untuk adaptasi untuk penghitungan simetri daripada algoritma yang dipublikasikan, yang didasarkan pada bias ke salah satu dari tiga sumbu kartesian.

Algoritma

Saya mulai dengan mengisi sel-sel bidang x, y, dan z dengan 1's, sedangkan sisanya berisi nol. Setelah selesai, saya membangun pola lapis demi lapis, dengan setiap lapisan berisi sel-sel yang memiliki jarak manhattan 3D umum dari asal. Sel hanya dapat berisi 1 jika tiga sel di bawahnya juga mengandung 1. jika ada di antara mereka yang mengandung 0, maka sel tersebut harus 0.

Keuntungan membangun pola dengan cara ini adalah bahwa setiap lapisan simetris tentang garis x = y = z. Ini berarti bahwa setiap lapisan dapat diperiksa secara independen untuk simetri.

Pemeriksaan simetri

Simetri padatan adalah sebagai berikut: 3 kali lipat rotasi tentang garis x = y = z -> 3 lipat rotasi tentang pusat segi enam; dan 3 x refleksi tentang 3 bidang yang berisi garis x = y = z dan masing-masing sumbu x, y, z -> refleksi tentang garis-garis melalui sudut-sudut segi enam.

Ini hanya menambah hingga 6 kali lipat simetri. Untuk mendapatkan simetri penuh segi enam, jenis simetri lain harus dipertimbangkan. Setiap padatan (dibangun dari 1's) memiliki padatan komplementer (dibangun dari 0's). Di mana N adalah aneh, padatan komplementer harus berbeda dari padatan asli (karena tidak mungkin bagi mereka untuk memiliki jumlah kubus yang sama). Namun ketika padatan komplementer diputar, akan ditemukan bahwa representasi 2D-nya sebagai ubin berlian identik (kecuali untuk operasi simetri 2 kali lipat) dengan padatan asli. Di mana N adalah genap, adalah mungkin bagi benda padat untuk menjadi terbalik sendiri.

Ini dapat dilihat pada contoh untuk N = 2 dalam pertanyaan. Jika dilihat dari kiri, segi enam pertama tampak seperti kubus padat dengan 8 kubus kecil, sedangkan segi enam terakhir tampak seperti kulit kosong dengan 0 kubus kecil. Jika dilihat dari kanan, kebalikannya benar. Segi 3, 4 dan 5 dan segi enam 16, 17 dan 18 tampak seperti mereka mengandung 2 atau 6 kubus, dan dengan demikian mereka saling melengkapi dalam 3 dimensi. Mereka terkait satu sama lain dalam 2 dimensi dengan operasi simetri 2 kali lipat (rotasi 2 kali lipat, atau refleksi tentang suatu sumbu melalui tepi segi enam.) Di sisi lain segi enam, ke-10, ke-11 dan ke-12 menunjukkan pola 3D yang adalah pelengkap mereka sendiri, dan karena itu memiliki simetri yang lebih tinggi (oleh karena itu ini adalah satu-satunya pola dengan multiplisitas ganjil).

Perhatikan bahwa memiliki (N ^ 3) / 2 kubus adalah kondisi yang diperlukan untuk melengkapi diri sendiri, tetapi secara umum itu bukan kondisi yang memadai jika N> 2. Hasil dari semua ini adalah bahwa untuk N aneh, tilings selalu terjadi berpasangan (N ^ 3) / 2 kubus harus diperiksa dengan cermat.

Kode saat ini (menghasilkan total yang tepat untuk N = 1,2,3,5. Kesalahan seperti yang didiskusikan untuk 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]);    
}

Keluaran

Program ini menghasilkan tabel keluaran 8 entri, sesuai dengan 8 simetri padatan. Padatan dapat memiliki salah satu dari 4 simetri sebagai berikut (notasi Schoenflies)

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)

Selain itu, ketika padatan memiliki tepat setengah sel dengan 1 dan setengah dengan 0, ada kemungkinan membalik semua 1 dan 0, kemudian membalikkan koordinat melalui pusat ruang kubus. Inilah yang saya sebut pelengkap diri, tetapi istilah yang lebih matematis akan menjadi "antisimetris sehubungan dengan pusat inversi."

Operasi simetri ini memberikan sumbu rotasi 2 kali lipat dalam ubin segi enam.

Pola yang memiliki simetri ini tercantum dalam kolom terpisah. Mereka hanya terjadi di mana N adalah genap.

Hitungan saya tampaknya sedikit tidak aktif untuk N = 4. Dalam diskusi dengan Peter Taylor, tampaknya saya tidak mendeteksi miring yang hanya memiliki simetri garis melalui tepi segi enam. Ini mungkin karena saya belum menguji komplemen diri (antisimetri) untuk operasi selain (inversi) x (identitas.) Pengujian komplemen mandiri untuk operator (inversi) x (refleksi) dan (inversi) x (rotasi 3 kali lipat ) dapat mengungkap simetri yang hilang. Saya kemudian akan mengharapkan baris pertama data untuk N = 4 terlihat seperti ini (16 lebih sedikit di c1 dan 32 lebih banyak di C1):

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

Ini akan membuat total sejalan dengan jawaban Peter dan https://oeis.org/A066931/a066931.txt

output saat ini adalah sebagai berikut.

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

Daftar tugas (diperbarui)

Rapikan kode saat ini.

Dilakukan, kurang lebih

Terapkan pemeriksaan simetri untuk lapisan saat ini, dan berikan parameter untuk simetri lapisan sebelumnya (tidak ada gunanya memeriksa apakah lapisan terakhir asimetris.)

Selesai, hasil untuk N aneh setuju dengan data yang dipublikasikan

Tambahkan opsi untuk menekan penghitungan angka asimetris (harus berjalan lebih cepat)

Ini dapat dilakukan dengan menambahkan kondisi lain ke panggilan rekursi: if(s1 && m<n*3-2)f(m + 1,e+d,s1)Ini mengurangi waktu lari untuk N = 5 dari 5 menit menjadi sekitar satu detik. Sebagai hasilnya, baris pertama dari output menjadi total sampah (seperti halnya total keseluruhan) tetapi jika total sudah diketahui dari OEIS, jumlah tiling asimetris dapat disusun kembali, setidaknya untuk N. aneh.

Tetapi bahkan untuk N, jumlah padatan asimetris (menurut simetri c3v) yang melengkapi diri sendiri akan hilang. Untuk kasus ini, program terpisah yang didedikasikan untuk padatan dengan tepat (N ** 3) / 2 sel dengan 1 mungkin berguna. Dengan ini tersedia (dan menghitung dengan benar) dimungkinkan untuk mencoba N = 6, tetapi akan membutuhkan waktu lama untuk dijalankan.

Terapkan penghitungan sel untuk mengurangi pencarian hingga (N ^ 3) / 2 kubus.

Tidak selesai, tabungan diharapkan menjadi marjinal

Terapkan simetri (komplementer padatan) memeriksa pola yang mengandung tepat (N ^ 3) / 2 kubus.

Selesai, tetapi tampaknya memiliki kelalaian, lihat N = 4.

Temukan cara untuk memilih angka terendah secara leksikal dari yang asimetris.

Penghematan tidak diharapkan menjadi sebesar itu. Menekan angka asimetris menghilangkan sebagian besar dari ini. Satu-satunya refleksi yang diperiksa adalah bidang melalui sumbu y (x dan z dihitung kemudian dengan mengalikan dengan 3.) Angka-angka dengan hanya simetri rotasi dihitung dalam kedua bentuk enansiomernya. Mungkin itu akan berjalan hampir dua kali lebih cepat jika hanya satu yang dihitung.

Untuk memfasilitasi ini, mungkin meningkatkan cara koordinat di setiap lapisan terdaftar (mereka membentuk kelompok degenerasi 6 atau 3, dengan kemungkinan sekelompok 1 di pusat tepat lapisan).

Menarik tapi mungkin ada pertanyaan lain di situs ini untuk dijelajahi.

Level River St
sumber