Algoritmo para gerar todos os conjuntos de m pontos na rede cúbica nxnxn que são únicos sob simetria

Estou implementando um algoritmo que será bastante computacionalmente complexo e quero tentar ter certeza de que não estou fazendo um trabalho desnecessário.

Existe uma rede cúbica nxnxn, por exemplo, se n = 2, isso consiste em (0,0,0), (0,1,0), (1,0,0), (1,1,0), (0, 1,1), (0,0,1), (1,0,1), (1,1,1).

A partir dessa estrutura, gerarei recursivamente todos os conjuntos de m pontos, algo como:

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

Isso pode ser chamado a partir de um set_of_points vazio.

A natureza do problema é tal que, na verdade, não preciso de toda permutação de m pontos, apenas os que são únicos sob as simetrias naturais do cubo.

Por exemplo, pegue um cubo 2x2x2 e suponha que queremos todos os conjuntos de 1 ponto. Sob o algoritmo básico acima, existem 8 conjuntos diferentes de 1 ponto.

No entanto, usando as simetrias do cubo, podemos reduzir isso para 1 conjunto único de 1 pontos, uma vez que todos os 8 originais são equivalentes sob simetrias do cubo (todos são 'cantos' neste caso).

Se o cubo for 2x2x2 em = 2, existem 28 conjuntos no algoritmo básico, mas isso reduz a apenas 3 sob simetria (por exemplo, {(0,0,0), (1,0,0)}, {(0 , 0,0), (1,1,0)}, {(0,0,0), (1,1,1)})

Obviamente, fazer o cálculo em 3 conjuntos de pontos é muito melhor que 28, então minha pergunta é: como faço para não gerar conjuntos de pontos que são simetricamente equivalentes a um conjunto já gerado? Ou, se isso não for possível, como posso ao menos reduzir um pouco o número de conjuntos.

(Observe - se m = 1 isso é relativamente fácil - basta escolher os pontos que estão mais próximos (0,0,0) do que qualquer um dos outros vértices, com um pouco de falsificação nos limites. É para m> 1 que isso ocorre ser um problema real)

Conceito básico:

(1) Podemos ver o ponto (0,0,0) simplesmente como 000. Cada ponto na rede agora cai em uma sequência simples. O primeiro ponto é 000, depois 001, 010 011 100 101 110 e 111. Essa é a ordem em que você tentará adicioná-los ao conjunto de pontos.

(2) Da mesma forma, o conjunto {(0,0,0), (0,0,1), (0,1,0)} pode ser simplesmente visto como 000001010 e o conjunto {(0,0,0) , (0,1,0), (0,0,1)} pode ser simplesmente visto como 000010001. Dois conjuntos diferentes não podem ter a mesma sequência e é possível visualizar facilmente 000001010 como numérico ou alfabeticamente menor que 000010001. Vamos chamar isso de valor definido. Todo conjunto possível de N pontos agora tem um valor definido, e todos os conjuntos possíveis de N pontos agora se enquadram em uma lista simples e bem ordenada.

(3) Todo grupo isomórfico de conjuntos de pontos possui exatamente um membro que terá o menor valor definido. Esses são os únicos onde realmente fazemos "computação útil".

(4) Aqui está a parte que precisará de um trabalho significativo. Antes de executar a solução (set_of_points + new_point), você deseja ver se algum isomorfismo reduziria o valor definido para set_of_points + new_point. Se algum isomorfismo abaixar o valor definido, este NÃO é um membro de valor mais baixo do conjunto isomórfico. Ignoramos qualquer trabalho neste new_point. Também estamos pulando todo o trabalho recursivo que teríamos feito dentro desta solução (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);
  }
 }
}

tomando a notação da resposta acima.

permite primeiro definir a simmertry proposta pela função rotate (direction, number_of_time)

solução:

(1) crie um hash de todo o conjunto da permutação com flag = 0 em cada um. por exemplo para n = 2, m = 2 000,001 = 0 000,010 = 0 000,011 = 0 ect '...

(2) inicie a partir do conjunto init, por exemplo i = 000.001

(3) gire o conjunto i para todas as direções usando a função de rotação (ou qualquer outra simetria que você desejar), por exemplo, a função de rotação deve ser chamada 24 vezes para cada permutação da rotação.

explicação: qualquer número de 1 a 6 pode estar na sua frente e cada número pode ser girado 4 vezes, portanto 6 * 4 = 24

(4) para cada conjunto retirado da combinação, defina o sinalizador de hash como 1 (ele já tem um conjunto simétrico)

(5) atualize i para o próximo conjunto, por exemplo, i = 000.010

(6) se o conjunto i no hash já estiver marcado, vá para (5) caso contrário, vá para (3)

terminamos quando todo o hash é marcado como 1.

Nota: Penso apenas em simetrias de espelho, não simetrias de rotação aqui.

Vamos supor que temos um (hiper) cubo de d dimensões, cada n unidade de comprimento (o cubo de Rubik seria d = 3, n = 3 ).

Um algoritmo ingênuo geraria n ^ d combinações de pontos e verificaria cada um para um confronto de simetria com todos os outros.

Se representarmos uma combinação de pontos como um vetor de bits n ^ d bits de comprimento, podemos usar um mapa (vetor de bits -> booleano) para marcar todas as simetrias do vetor de bits como true . Poderíamos então pular uma combinação se ela já estiver marcada no mapa.

Essa abordagem é muito ineficiente em termos de espaço: é necessário um mapa com 2 ^ (n ^ d) entradas, ou seja, um bitmap com tantos bits. (Para o cubo de Rubik, seria 2 ^ 27 = 128Mbit = 16 Mbytes.)

Só podemos lembrar as representações canônicas, ou seja, vetores de bits que possuem o menor valor inteiro, se representados como uma palavra não assinada com n ^ d bits. Quando geramos uma nova permutação de pontos, geramos todas as suas simetrias e só verificamos se vimos a simetria com o menor valor numérico. Isso nos permitirá armazenar um mapa com apenas 2 ^ n bits (apenas 1 byte para o cubo de Rubik), porque temos simetrias em 2 ^ d . No entanto, nos faz gerar essas simetrias 2 ^ d em cada etapa, portanto gastamos O (2 ^ (d ^ n + d)) = O (2 ^ (d ^ n) * 2 ^ d) tempo. Ainda pobre.

Podemos aplicar a idéia do parágrafo anterior ao caso unidimensional. Para gerar todas as combinações em um vetor de comprimento d , podemos apenas incrementar um número binário d bits, começando por todos os 0s. Vamos dividir nosso vetor em dois segmentos d / 2- longos, por exemplo, esquerda e direita. Podemos notar que, para cada 1bit no segmento esquerdo, precisamos apenas ver combinações que possuem 1bit na posição simétrica da seção direita. Caso contrário, já teríamos gerado uma combinação simétrica anteriormente, quando as posições dos bits foram trocadas e a 0anterior 1. Dessa forma, para cada posição de bit na metade direita (r) e a posição simétrica na metade esquerda(l) precisamos apenas gerar 3 combinações: (l = 0, r = 0); (l = 1, r = 1); (l = 1, r = 0) . Assim, precisamos apenas gerar 2 ^ (d / 2) permutações de um vetor de comprimento d , produzindo 3 combinações para cada permutação.

Um cubo de d dimensões pode ser construído de vetores n ^ (d-1) . O truque acima nos dá os vetores mais baratos que a abordagem ingênua. Para gerar um cubo, precisamos de tempo O (n ^ (d-1) * 2 ^ (d / 2)) .

Se olharmos para o cubo ao longo da dimensão de nossos vetores unidimensionais, podemos ver que não precisamos verificar simetria nessa dimensão: ao gerar os cubos, eliminamos simetrias para cada vetor envolvido.

Agora, se olharmos toda esta dimensão, podemos reutilizar o mesmo truque.

Quando olhamos através, olhamos, por exemplo, os primeiros bits de vetores que formam um plano específico. Esses bits representam um vetor de bits unidimensional. Podemos eliminar a maioria das combinações de seus bits por razões de simetria, como descrito acima. Portanto, se escolhermos um vetor 1-d específico de um cubo (por exemplo, mais à esquerda, no topo), podemos eliminar muitos vetores do mesmo plano (por exemplo, ao topo) com base no valor de um bit específico. Portanto, para um vetor em uma posição simétrica no espelho no plano, podemos evitar que todas as combinações possam ter esse bit definido (ou não definido), reduzindo drasticamente o número de vetores que precisamos gerar para um plano específico. Cada bit eliminado reduz pela metade o número de vetores possíveis na posição refletida no espelho. Isso nos dá uma sequência de planos sem contrapartidas simétricas ao longo de cada dimensão.

Esse truque pode ser aplicado para limitar ainda mais a geração de permutações dos seguintes planos ao longo de uma terceira dimensão, etc.

Embora não seja um algoritmo completo, espero que isso ajude.