La comparación de las colecciones de subconjuntos hasta permutación

Question

I tiene una matriz a [i] [j]. Los elementos son char, interpretado como subconjuntos del conjunto {1, ..., 8} (el elemento k está en el subconjunto Si el bit k-ésimo es 1). Creo que no es relevante, pero cada elemento ha establecido exactamente 4 bits.

Cada fila a [1] [j] .. a [n] [j] es una colección de subconjuntos de {1, ..., 8}. Necesito quitar las filas duplicadas, en las dos filas se consideran duplicados si se puede obtener a partir de la otra por una permutación de {1, ..., 8}.

Ejemplo (0bxxxxxxxx significa número binario):

0b11000000, 0b01100000, 0b00110000

es un duplicado de

0b00110000, 0b00011000, 0b00100100

porque el primero se puede obtener de este último mediante la aplicación de la permutación

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6

y reordenando el resultado.

Para consideraciones de rendimiento, la matriz contiene aproximadamente 2000 filas, cada una que comprende en la mayoría de 20 elementos. Cada fila ya está ordenado, y las filas están en orden creciente lexicográfico, si esto podría ayudar. El resto del algoritmo está escrito en C, por lo que sería preferible una solución C.

Gracias por su ayuda.

Answer 1

Si todos los subconjuntos tenían 2 elementos, esto representaría gráfico isomorfismo , con los subconjuntos representando los bordes del gráfico. Esto es aún más general (por lo tanto probablemente más difícil), por lo que me vería en heurística utilizada para resolver isomorfismo de grafos y ver si se aplican aquí.

Hay una gran cantidad de heurísticas gráfico-isomorfismo que pueden excluir barata isomorfismo. Para una colección particular, puede calcular cuántos subconjuntos no cada elemento pertenece, a continuación, ordenar eso. En su ejemplo, ambas colecciones obtendrían [2,2,1,1,0,0,0,0]. Si las secuencias ordenadas de dos colecciones son diferentes, entonces no hay isomorfismo. Por supuesto, la igualdad no garantiza que no existe.

Hay muchas heurística más similares que son incluso mejores en el tamizado a cabo grafos no isomorfos (y, posiblemente, podrían aplicarse aquí).

Además, 8! sólo es 40.320, por lo fuerza bruta todas las permutaciones no es totalmente inviable.