Confrontando le collezioni di sottoinsiemi fino a permutazione
-
21-08-2019 - |
Domanda
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.
Soluzione
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.