Algorytm generujący wszystkie zestawy m punktów w sieci sześciennej nxnxn, które są unikalne w symetrii

Wdrażam algorytm, który będzie dość skomplikowany obliczeniowo, i chcę się upewnić, że nie wykonuję niepotrzebnej pracy.

Istnieje sieć sześcienna nxnxn, np. Jeśli n = 2, to składa się z (0,0,0), (0,1,0), (1,0,0), (1,1,0), (0, 1,1), (0,0,1), (1,0,1), (1,1,1).

Z tej sieci będę rekurencyjnie generować wszystkie zestawy m punktów, coś w stylu:

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

Można to następnie wywołać zaczynając od pustych set_of_points.

Charakter problemu jest taki, że tak naprawdę nie potrzebuję każdej permutacji punktów m, tylko tych, które są unikalne pod naturalną symetrią sześcianu.

Na przykład weź sześcian 2x2x2 i załóżmy, że chcemy wszystkich zbiorów 1 punktu. Zgodnie z powyższym algorytmem podstawowym istnieje 8 różnych zestawów 1 punktu.

Jednak używając symetrii sześcianu, możemy zmniejszyć to do 1 unikalnego zestawu 1 punktów, ponieważ wszystkie oryginalne 8 są równoważne pod symetriami sześcianu (w tym przypadku wszystkie są „narożnikami”).

Jeśli sześcian ma wymiary 2x2x2 i m = 2, w algorytmie podstawowym jest 28 zestawów, ale zmniejsza się do zaledwie 3 przy symetrii (np. {(0,0,0), (1,0,0)}, {(0 , 0,0), (1,1,0)}, {(0,0,0), (1,1,1)})

Oczywiście wykonanie obliczeń na 3 zestawach punktów jest znacznie lepsze niż 28, więc moje pytanie brzmi: jak mogę generować zestawy punktów, które są symetrycznie równoważne zestawowi już wygenerowanemu? Lub jeśli nie jest to możliwe, w jaki sposób mogę choć trochę zmniejszyć liczbę zestawów.

(Uwaga - jeśli m = 1 jest to stosunkowo łatwe - po prostu wybierz punkty, które są bliższe (0,0,0) niż którykolwiek z pozostałych wierzchołków, z niewielkim przesunięciem na granicach. To dla m> 1 to dostaje być prawdziwym problemem)

Podstawowy pomysł:

(1) Możemy zobaczyć punkt (0,0,0) po prostu jako 000. Każdy punkt w sieci jest teraz objęty prostą sekwencją. Pierwszy punkt to 000, następnie 001, a następnie 010 011 100 101 110 i 111. W tej kolejności spróbujesz dodać je do zestawu punktów.

(2) Podobnie zbiór {(0,0,0), (0,0,1), (0,1,0)} można po prostu postrzegać jako 000001010, a zbiór {(0,0,0) , (0,1,0), (0,0,1)} można po prostu postrzegać jako 000010001. Dwa różne zestawy nie mogą mieć tej samej sekwencji i można łatwo wyświetlić 000001010 jako numerycznie lub alfabetycznie mniej niż 000010001. Nazwijmy to ustawioną wartością. Każdy możliwy zestaw N punktów ma teraz ustawioną wartość, a wszystkie możliwe zestawy N punktów należą teraz do prostej, dobrze uporządkowanej listy.

(3) Każda izomorficzna grupa zestawów punktów ma dokładnie jeden element, który będzie miał najniższą wartość zestawu. Są to jedyne, w których faktycznie wykonujemy „przydatne obliczenia”.

(4) Oto część, która będzie wymagała znacznej pracy. Zanim uruchomisz rozwiązanie (set_of_points + new_point), chcesz sprawdzić, czy jakiś izomorfizm obniżyłby wartość ustawioną dla set_of_points + new_point. Jeśli jakikolwiek izomorfizm obniżyłby ustawioną wartość, NIE jest to element o najniższej wartości w zestawie izomorficznym. Pomijamy wykonywanie jakiejkolwiek pracy nad tym new_point. Pomijamy również całą rekurencyjną pracę, którą wykonalibyśmy w ramach tego rozwiązania (set_of_points, kandydat_punkt).

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

biorąc pod uwagę powyższą odpowiedź.

pozwala najpierw zdefiniować symmertry zaproponowane przez funkcję obrotu (kierunek, liczba_czasu)

rozwiązanie:

(1) utwórz hash całego zestawu permutacji z flagą = 0 na każdym. na przykład dla n = 2, m = 2 000,001 = 0 000,010 = 0 000,011 = 0 ect '...

(2) zacznij od zestawu inicjującego, na przykład i = 000,001

(3) obróć zestaw i we wszystkich kierunkach za pomocą funkcji obracania (lub dowolnej innej symetrii, na przykład), funkcja obracania powinna być wywoływana 24 razy dla każdej permutacji obrotu.

wyjaśnienie: dowolna liczba 1-6 może znajdować się przed tobą i każda z liczb może być obracana 4 razy, dlatego 6 * 4 = 24

(4) dla każdego zestawu returened z kombinacji ustaw flagę hash na 1 (ma już zestaw symetryczny)

(5) zaktualizuj i do następnego zestawu, na przykład i = 000,010

(6) jeśli zestaw i w haszu jest już zaznaczony, przejdź do (5), w przeciwnym razie przejdź do (3)

skończymy, gdy cały skrót jest oznaczony jako 1.

Uwaga: myślę tylko o symetriach lustrzanych, a nie symetriach obrotowych.

Załóżmy, że mamy (hiper) sześcian d wymiarów, każdy n jednostek długości (sześcian Rubika będzie d = 3, n = 3 ).

Naiwny algorytm generowałby n + d kombinacji punktów i sprawdzał, czy nie ma kolizji symetrii ze wszystkimi innymi.

Jeśli reprezentujemy kombinację punktów jako wektor bitowy o długości n ^ d bitów, możemy użyć mapy (wektor bitowy -> wartość logiczna), aby oznaczyć wszystkie symetrie wektora bitowego wartością true . Możemy wtedy pominąć kombinację, jeśli jest już zaznaczona na mapie.

To podejście jest bardzo nieefektywne przestrzennie: wymaga mapy z 2 ^ (n ^ d) wpisami, czyli bitmapy z tak wieloma bitami. (Dla kostki Rubika byłoby to 2 ^ 27 = 128 Mb = 16 Mb.)

Możemy zapamiętać tylko reprezentacje kanoniczne, to znaczy takie wektory bitowe, które mają najmniejszą wartość całkowitą, jeśli są reprezentowane jako n-d- bez znaku słowo. Kiedy generujemy nową permutację punktów, generujemy wszystkie jej symetrie i sprawdzamy tylko, czy widzieliśmy symetrię o najmniejszej wartości liczbowej. To pozwoli nam przechowywać mapę tylko z 2 ^ n bitami (tylko 1 bajt dla kostki Rubika), ponieważ mamy 2 ^ d symetrie. Zmusza nas to do generowania symetrii 2 ^ d na każdym kroku, więc spędzamy czas O (2 ^ (d ^ n + d)) = O (2 ^ (d ^ n) * 2 ^ d) . Wciąż biedny.

Możemy zastosować pomysł z poprzedniego akapitu do przypadku 1-wymiarowego. Aby wygenerować wszystkie kombinacje w wektorze o długości d , możemy po prostu zwiększyć liczbę binarną d bitów, zaczynając od wszystkich 0s. Podzielmy nasz wektor na dwa długie segmenty d / 2 , np. Lewy i prawy. Możemy zauważyć, że dla każdego 1bitu w lewym segmencie musimy zobaczyć tylko kombinacje, które mają 1bity w symetrycznej pozycji prawej sekcji. W przeciwnym razie wygenerowalibyśmy już symetryczną kombinację wcześniej, gdy pozycje bitów zostały zamienione, i 0pojawiły się przed 1. W ten sposób dla każdej pozycji bitu w prawej połowie (r) i pozycji symetrycznej w lewej połowie(l) musimy wygenerować tylko 3 kombinacje: (l = 0, r = 0); (l = 1, r = 1); (l = 1, r = 0) . Dlatego musimy wygenerować tylko 2 ^ (d / 2) permutacji wektora o długości d , uzyskując 3 kombinacje dla każdej permutacji.

Sześcian d wymiarów może być zbudowany z n ^ (d-1) wektorów. Powyższa sztuczka daje nam wektory tańsze niż naiwne podejście. Aby wygenerować sześcian, potrzebujemy czasu O (n ^ (d-1) * 2 ^ (d / 2)) .

Jeśli spojrzymy na sześcian wzdłuż wymiaru naszych wektorów 1-wymiarowych, zobaczymy, że nie musimy sprawdzać symetrii wzdłuż tego wymiaru: generując kostki eliminujemy symetrie dla każdego zaangażowanego wektora.

Teraz, gdy spojrzymy na ten wymiar, możemy ponownie użyć tej samej sztuczki.

Kiedy patrzymy w poprzek, patrzymy np. Na pierwsze fragmenty wektorów tworzących konkretną płaszczyznę. Te bity reprezentują 1-wymiarowy wektor bitowy. Możemy wyeliminować większość kombinacji jego bitów z powodów symetrii, jak opisano powyżej. Więc jeśli wybieramy konkretny wektor 1-d sześcianu (np. Skrajnie lewy najwyższy), możemy wyeliminować wiele wektorów tej samej płaszczyzny (np. Górny) na podstawie wartości określonego bitu. Tak więc dla wektora w lustrzanej symetrycznej pozycji na płaszczyźnie możemy uniknąć generowania wszystkich kombinacji, które mogą mieć ten bit ustawiony (lub nieustawiony), co drastycznie zmniejsza liczbę wektorów, które musimy wygenerować dla konkretnej płaszczyzny. Każdy wyeliminowany bit zmniejsza o połowę liczbę możliwych wektorów w pozycji odbicia lustrzanego. To daje nam sekwencję płaszczyzn bez symetrycznych odpowiedników wzdłuż każdego wymiaru.

Tę sztuczkę można zastosować w celu dalszego ograniczenia generowania permutacji następujących płaszczyzn wzdłuż trzeciego wymiaru itp.

Chociaż nie jest to kompletny algorytm, mam nadzieję, że to pomaga.