Algoritma untuk menghasilkan semua set poin m dalam kisi kubik nxnxn yang unik di bawah simetri

Saya menerapkan algoritma yang akan menjadi sangat kompleks secara komputasi, dan ingin mencoba memastikan saya tidak melakukan pekerjaan yang tidak perlu.

Ada kisi kubik nxnxn, misalnya jika n = 2 ini terdiri dari (0,0,0), (0,1,0), (1,0,0), (1,1,0), (0, 1,1), (0,0,1), (1,0,1), (1,1,1).

Dari kisi ini saya akan secara rekursif menghasilkan semua set poin m, sesuatu seperti:

solve(set_of_points) {
     if set_of_points.size = m, finish

     do some useful computation here

     for each point in lattice not in set_of_points:
         solve(set_of_points + new_point);
}

Ini kemudian dapat disebut dimulai dengan set_of_points kosong.

Sifat masalah adalah sedemikian rupa sehingga saya tidak benar-benar membutuhkan setiap permutasi poin m, hanya yang unik di bawah simetri alami kubus.

Misalnya, ambil kubus 2x2x2 dan anggap kita ingin semua set 1 poin. Di bawah algoritma dasar di atas, ada 8 set 1 poin yang berbeda.

Namun, dengan menggunakan simetri kubus kita dapat mengurangi ini ke 1 set unik 1 poin, karena semua 8 asli setara dengan simetri kubus (mereka semua 'sudut' dalam kasus ini).

Jika kubusnya 2x2x2 dan m = 2, ada 28 set dalam algoritma dasar, tetapi ini berkurang menjadi hanya 3 di bawah simetri (misalnya {(0,0,0), (1,0,0)}, {(0 , 0,0), (1,1,0)}, {(0,0,0), (1,1,1)})

Jelas melakukan perhitungan pada 3 set poin jauh lebih baik dari 28, jadi pertanyaan saya adalah bagaimana saya tidak menghasilkan set poin yang secara simetris sama dengan set yang sudah dihasilkan? Atau jika ini tidak memungkinkan, bagaimana saya setidaknya mengurangi jumlah set sedikit.

(Catatan - jika m = 1 ini relatif mudah - cukup pilih titik yang lebih dekat (0,0,0) daripada simpul lainnya, dengan sedikit fudging pada batas-batasnya. Untuk m> 1 ini didapat menjadi masalah nyata)

Konsep dasar:

(1) Kita dapat melihat titik (0,0,0) hanya sebagai 000. Setiap titik dalam kisi sekarang jatuh dalam urutan sederhana. Poin pertama adalah 000, lalu 001, lalu 010 011 100 101 110 dan 111. Ini adalah urutan yang akan Anda coba tambahkan ke set-point.

(2) Demikian pula, himpunan {(0,0,0), (0,0,1), (0,1,0)} dapat dengan mudah dilihat sebagai 000001010, dan himpunan {(0,0,0) , (0,1,0), (0,0,1)} dapat dengan mudah dilihat sebagai 000010001. Dua set berbeda tidak dapat memiliki urutan yang sama, dan Anda dapat dengan mudah melihat 000001010 secara numerik atau abjad kurang dari 000010001. Sebut ini nilai set. Setiap set poin N yang mungkin sekarang memiliki nilai set, dan semua set poin N yang mungkin sekarang termasuk dalam daftar sederhana yang disusun dengan baik.

(3) Setiap kelompok set poin isomorfik memiliki tepat satu anggota yang akan memiliki nilai set terendah. Hanya itulah satu-satunya tempat kami melakukan "perhitungan bermanfaat".

(4) Inilah bagian yang perlu kerja keras. Sebelum Anda menjalankan pemecahan (set_of_points + new_point), Anda ingin melihat apakah ada isomorfisma yang akan menurunkan nilai set untuk set_of_points + new_point. Jika ada isomorfisme akan menurunkan nilai yang ditetapkan maka ini BUKAN anggota nilai terendah dari set isomorfik. Kami lewati melakukan pekerjaan apa pun di new_point ini. Kami juga melewatkan semua pekerjaan rekursif yang akan kami lakukan di dalam penyelesaian ini (set_of_points, kandidat_point).

solve(set_of_points,new_point) {
 set_of_points = set_of_points + new_point
 do some useful computation here
 if set_of_points.size = m, compute how many isomophisms exist, apply that multiple, finish
 for(candidate_point = new_point+1 to last_point) { /skips point-permutations for free!/
  if ISOMORPH_TESTS_CANNOT_LOWER_VALUE_OF(set_of_points+candidate_point) {
   solve(set_of_points,candidate_point);
  }
 }
}

mengambil notasi dari jawaban di atas.

pertama mari kita mendefinisikan symmertry yang diusulkan oleh fungsi rotate (direction, number_of_time)

larutan:

(1) membuat hash dari semua set permutasi dengan flag = 0 pada masing-masing. misalnya untuk n = 2, m = 2 000.001 = 0 000.010 = 0 000.011 = 0 dll '...

(2) mulai dari set init, misalnya i = 000.001

(3) putar set i ke semua arah menggunakan fungsi rotate (atau simetri lain yang Anda suka) misalnya, fungsi rotate harus memanggil 24 kali untuk setiap permutasi rotasi.

penjelasan: angka 1-6 dapat berada di depan Anda dan setiap angka dapat diputar 4 kali, oleh karena itu 6 * 4 = 24

(4) untuk setiap set yang diambil dari kombinasi, atur bendera hash ke 1 (sudah set simetris)

(5) perbarui i ke set berikutnya misalnya i = 000.010

(6) jika himpunan i dalam hash sudah ditandai, lanjutkan ke (5) sebaliknya ke (3)

kita selesai ketika semua hash ditandai sebagai 1.

Catatan: Saya hanya memikirkan tentang simetri cermin, bukan simetri rotasi di sini.

Misalkan kita memiliki kubus (hiper) dimensi d , masing-masing n satuan panjang (kubus Rubik adalah d = 3, n = 3 ).

Algoritma yang naif akan menghasilkan n ^ d kombinasi poin, dan memeriksa masing-masing untuk bentrokan simetri dengan semua orang lain.

Jika kita merepresentasikan kombinasi titik sebagai vektor bit n ^ d bit, kita dapat menggunakan peta (bit vector -> boolean) untuk menandai semua simetri vektor bit dengan true . Kami kemudian dapat melewatkan kombinasi jika sudah ditandai di peta.

Pendekatan ini sangat tidak efisien ruang: dibutuhkan peta dengan entri 2 ^ (n ^ d) , yaitu, bitmap dengan banyak bit ini. (Untuk kubus Rubik, itu akan menjadi 2 ^ 27 = 128Mbit = 16 Mbytes.)

Kita hanya bisa mengingat representasi kanonik, yaitu, bit vektor sehingga memiliki nilai integer terkecil, jika direpresentasikan sebagai n ^ d -bit kata unsigned. Ketika kami menghasilkan permutasi poin baru, kami menghasilkan semua simetri, dan hanya memeriksa apakah kami telah melihat simetri dengan nilai numerik terkecil. Ini akan memungkinkan kita untuk menyimpan peta dengan hanya 2 ^ n bit (hanya 1 byte untuk kubus Rubik), karena kita memiliki 2 ^ d simetri. Itu membuat kita menghasilkan simetri 2 ^ d ini pada setiap langkah, jadi kita menghabiskan waktu O (2 ^ (d ^ n + d)) = O (2 ^ (d ^ n) * 2 ^ d) waktu. Masih miskin.

Kita dapat menerapkan ide dari paragraf sebelumnya ke kasus 1 dimensi. Untuk menghasilkan semua kombinasi dalam vektor dengan panjang d , kita bisa menambahkan angka biner d bit, mulai dari semua 0s. Mari kita membagi vektor kita menjadi dua segmen panjang d / 2 , mis. Kiri dan kanan. Kita dapat melihat bahwa untuk setiap 1bit di segmen kiri kita hanya perlu melihat kombinasi yang memiliki 1bit dalam posisi simetris pada bagian kanan. Kalau tidak, kita akan sudah menghasilkan kombinasi simetris sebelumnya, ketika posisi bit ditukar, dan yang 0datang sebelum 1. Dengan cara ini, untuk setiap posisi bit di bagian kanan (r) , dan posisi simetris di bagian kiri(l) kita hanya perlu menghasilkan 3 kombinasi: (l = 0, r = 0); (l = 1, r = 1); (l = 1, r = 0) . Jadi kita hanya perlu menghasilkan 2 ^ (d / 2) permutasi dari vektor dengan panjang d , menghasilkan 3 kombinasi untuk setiap permutasi.

Kubus dimensi d dapat dibangun dari vektor n ^ (d-1) . Trik di atas memberi kita vektor lebih murah daripada pendekatan naif. Untuk menghasilkan kubus, kita membutuhkan waktu O (n ^ (d-1) * 2 ^ (d / 2)) .

Jika kita melihat kubus di sepanjang dimensi vektor 1-dimensi kita, kita dapat melihat bahwa kita tidak perlu memeriksa simetri di sepanjang dimensi ini: saat menghasilkan kubus, kita menghilangkan simetri untuk setiap vektor yang terlibat.

Sekarang jika kita melihat di dimensi ini, kita dapat menggunakan kembali trik yang sama.

Ketika kita melihat ke seberang, kita melihat misalnya bit pertama vektor yang membuat bidang tertentu. Bit-bit ini mewakili vektor bit 1-dimensi. Kita dapat menghilangkan sebagian besar kombinasi bitnya dari alasan simetri, seperti dijelaskan di atas. Jadi jika kita memilih vektor 1-d tertentu dari sebuah kubus (misalnya paling kiri paling atas), kita dapat menghilangkan banyak vektor dari bidang yang sama (misalnya atas) berdasarkan pada nilai bit tertentu. Jadi untuk vektor dalam posisi cermin-simetris pada bidang, kita dapat menghindari menghasilkan semua kombinasi yang mungkin memiliki set bit (atau tidak disetel), mengurangi jumlah vektor yang harus kita hasilkan untuk bidang tertentu secara drastis. Setiap bit yang dihilangkan membagi dua jumlah vektor yang mungkin pada posisi cermin. Ini memberi kita urutan pesawat tanpa pasangan simetris di sepanjang setiap dimensi.

Trik ini dapat diterapkan untuk membatasi generasi permutasi lebih lanjut dari pesawat berikut sepanjang dimensi ketiga, dll.

Meskipun bukan algoritma yang lengkap, saya harap ini membantu.