Confrontando le collezioni di sottoinsiemi fino a permutazione

Question

Ho un array a [i] [j]. Gli elementi sono char, interpretati come sottoinsiemi dell'insieme {1, ..., 8} (l'elemento k è nel sottoinsieme se il bit k-esimo è 1). Non credo sia rilevante, ma ogni elemento ha esattamente 4 bit impostati.

Ogni riga un [1] [j] .. a [n] [j] è una collezione di sottoinsiemi di {1, ..., 8}. Ho bisogno di rimuovere le righe duplicate, dove due righe vengono considerati duplicati se uno può essere ottenuta presso l'altro da una permutazione di {1, ..., 8}.

Esempio (0bxxxxxxxx significa numero binario):

0b11000000, 0b01100000, 0b00110000

è un duplicato di

0b00110000, 0b00011000, 0b00100100

perché il primo può essere ottenuto da quest'ultimo applicando la permutazione

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

e riordinare il risultato.

Per considerazioni di prestazioni, l'array contiene circa 2000 righe, ciascuna comprendente al massimo 20 elementi. Ogni riga è già ordinata, e anche le righe sono in ordine crescente lessicografico, se questo potrebbe aiutare. Il resto dell'algoritmo è scritto in C, quindi una soluzione C sarebbe preferibile.

Grazie per il vostro aiuto.

Answer 1

Se tutti i sottoinsiemi avevano 2 elementi, ciò rappresenterebbe grafi , con i sottoinsiemi rappresenta bordi del grafico. Questo è ancora più generale (e quindi probabilmente più difficile), quindi mi piacerebbe guardare euristiche utilizzate per risolvere grafico isomorfismo e vedere se si applicano qui.

Ci sono un sacco di euristica grafico-isomorfismo che può a buon mercato escludere isomorfismo. Per una particolare collezione, è possibile calcolare il numero di sottoinsiemi fa ogni elemento appartiene, quindi ordinare quello. Nel tuo esempio, entrambe le collezioni otterrebbe [2,2,1,1,0,0,0,0]. Se le sequenze ordinate per due collezioni sono diversi, allora non c'è isomorfismo. Naturalmente l'uguaglianza non garantisce che ci sia.

Ci sono molte euristiche più simili che sono ancora meglio a setacciatura out grafici non isomorfi (e potrebbe applicare qui).

Inoltre, 8! è soltanto 40320, così bruta costringendo tutte le permutazioni non è totalmente irrealizzabile.