Algoritmo per generare tutti i gruppi di m punti in n x n x n reticolo cubico che sono unici sotto simmetria

Concetto di base:

(1) Possiamo vedere il punto (0,0,0) semplicemente come 000. Ogni punto nel reticolo ora cade in una semplice sequenza. Il primo punto è 000, quindi 001, quindi 010 011 100 101 110 e 111. Questo è l'ordine in cui tenterai di aggiungerli al set point.

(2) Allo stesso modo, l'insieme {(0,0,0), (0,0,1), (0,1,0)} può essere semplicemente visto come 000001010, e l'insieme {(0,0 , 0), (0,1,0), (0,0,1)} può essere semplicemente visto come 000010001. Due insiemi diversi non possono avere la stessa sequenza, e si può facilmente vedere 000001010 come numericamente o alfabeticamente meno di 000010001. Chiamiamo questo valore impostato. Ogni possibile insieme di N punti ora ha un valore impostato, e tutti i possibili insiemi di N punti ora cadono in un semplice elenco ben ordinato.

(3) Ogni gruppo isomorfo di insiemi di punti ha esattamente un membro che avrà il valore impostato più basso. Quelli sono gli unici in cui effettivamente realizziamo "calcoli utili".

(4) Ecco la parte che richiederà un lavoro significativo. Prima di eseguire risolvi (set_of_points + new_point), vuoi vedere se qualche isomorfismo abbasserebbe il valore impostato per set_of_points + new_point. Se qualsiasi isomorfismo abbasserebbe il valore impostato, questo NON è un membro del valore più basso dell'insieme isomorfico. Saltiamo qualsiasi lavoro su questo nuovo punto. Stiamo anche saltando tutto il lavoro ricorsivo che avremmo fatto all'interno di questa soluzione (set_of_points, candidate_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);
  }
 }
}

prendendo la notazione della risposta sopra.

consente innanzitutto di definire la simmertry proposta dalla funzione ruota (direzione, numero_di_tempo)

soluzione:

(1) crea l'hash di tutto il set della permutazione con flag = 0 su ciascuno. per esempio per n = 2, m = 2 000,001 = 0 000,010 = 0 000,011 = 0 ect '...

(2) inizia da init set, ad esempio i = 000,001

(3) ruota l'insieme i in tutte le direzioni usando la funzione di rotazione (o qualsiasi altra simmetria che ti piace) per esempio, la funzione di rotazione dovrebbe essere chiamata 24 volte per ogni permutazione della rotazione.

explenation: qualsiasi numero 1-6 può essere di fronte a te e ognuno dei numeri può essere ruotato 4 volte, quindi 6 * 4 = 24

(4) per ogni set ripristinato dalla combinazione, imposta il flag di hash su 1 (è già impostato simmetrico)

(5) aggiorna i alla serie successiva ad esempio i = 000.010

(6) se l'insieme i nella hash è già segnato, vai a (5) altrimenti vai a (3)

abbiamo finito quando tutti gli hash sono contrassegnati come 1.

Nota: penso solo alle simmetrie speculari, non alle simmetrie di rotazione qui.

Supponiamo di avere un (iper) cubo di dimensioni d , ciascuna unità n (un cubo di Rubik sarebbe d = 3, n = 3 ).

Un algoritmo ingenuo genera combinazioni di punti n ^ d e controlla ciascuna di esse per uno scontro di simmetria con tutte le altre.

Se rappresentiamo una combinazione di punti come bit bit di vettore n ^ d , possiamo usare una mappa (bit vector - > boolean) per marcare tutte le simmetrie del vettore bit con true . Potremmo quindi saltare una combinazione se è già segnata nella mappa.

Questo approccio è molto poco efficiente in termini di spazio: prende una mappa con voci 2 ^ (n ^ d) , cioè una bitmap con tanti bit. (Per il cubo di Rubik, sarebbe 2 ^ 27 = 128 Mbit = 16 Mbyte.)

Possiamo solo ricordare le rappresentazioni canoniche, cioè quei vettori bit che hanno il valore intero più piccolo, se rappresentato come una parola senza segno n ^ d . Quando generiamo una nuova permutazione di punti, generiamo tutte le sue simmetrie e controlliamo solo se abbiamo visto la simmetria con il valore numerico più piccolo. Questo ci permetterà di memorizzare una mappa con solo 2 ^ n bit (solo 1 byte per il cubo di Rubik), perché abbiamo 2 ^ d simmetrie. Ci fa generare queste simmetrie 2 ^ d su ogni passaggio, tuttavia, quindi spendiamo O (2 ^ (d ^ n + d)) = O (2 ^ (d ^ n) * 2 ^ d) orario. Ancora povero.

Possiamo applicare l'idea dal paragrafo precedente al caso 1-dimensionale. Per generare tutte le combinazioni in un vettore di lunghezza d , possiamo semplicemente incrementare i bit di un numero binario d , partendo da tutti 0 s. Dividiamo il nostro vettore a due segmenti d / 2 -lungo, ad es. sinistra e destra. Possiamo notare che per ogni 1 bit nel segmento sinistro abbiamo solo bisogno di vedere combinazioni che hanno 1 bit nella posizione simmetrica della sezione destra. Altrimenti avremmo già generato una combinazione simmetrica prima, quando le posizioni dei bit sono state scambiate e il 0 è arrivato prima del 1 . In questo modo, per ogni posizione di bit nella parte destra (r) , e nella posizione simmetrica nella metà sinistra (l) abbiamo solo bisogno di generare 3 combinazioni: (l = 0, r = 0); (l = 1, r = 1); (l = 1, r = 0) . Quindi abbiamo solo bisogno di generare permute 2 ^ (d / 2) di un vettore di lunghezza d , ottenendo 3 combinazioni per ogni permutazione.

Un cubo di dimensioni d può essere costruito con i vettori n ^ (d-1) . Il trucco sopra ci dà i vettori più economici rispetto all'approccio ingenuo. Per generare un cubo, abbiamo bisogno di O (n ^ (d-1) * 2 ^ (d / 2)) tempo.

Se osserviamo il cubo lungo la dimensione dei nostri vettori monodimensionali, possiamo vedere che non dobbiamo controllare la simmetria lungo questa dimensione: mentre generiamo i cubi, eliminiamo le simmetrie per ciascun vettore coinvolto.

Ora se guardiamo attraverso questa dimensione, possiamo riutilizzare lo stesso trucco.

Quando guardiamo attraverso, guardiamo ad es. primi bit di vettori che fanno un piano particolare. Questi bit rappresentano un vettore di bit 1-dimensionale. Possiamo eliminare la maggior parte delle combinazioni dei suoi bit da motivi di simmetria, come descritto sopra. Quindi, se selezioniamo un particolare vettore 1-d di un cubo (ad esempio il più a sinistra più in alto), possiamo eliminare molti vettori dello stesso piano (ad esempio in alto) in base al valore di un particolare bit. Quindi, per un vettore in una posizione speculare simmetrica sul piano, possiamo evitare di generare tutte le combinazioni che potrebbero avere quel bit impostato (o non impostato), riducendo drasticamente il numero di vettori che dobbiamo generare per un particolare piano. Ogni bit eliminato dimezza il numero di vettori possibili nella posizione riflessa nello specchio. Questo ci dà una sequenza di piani senza controparti simmetriche lungo ogni dimensione.

Questo trucco può essere applicato per limitare ulteriormente la generazione di permutazioni dei seguenti piani lungo una terza dimensione, ecc.

Sebbene non sia un algoritmo completo, spero che questo aiuti.