Esiste un algoritmo per generare tutte le permutazioni circolari uniche di un multiset?

StackOverflow https://stackoverflow.com/questions/3467914

Domanda

ho incontrato questo problema quando si fa un po 'di programmazione entusiasta. Il problema può essere espresso come segue:

  

Per un un multiset, sia P (A) il   insieme di tutte le possibili permutazioni di A.   P (A) è naturalmente diviso in   sottoinsiemi disgiunti che sono l'equivalenza   classi, con la relazione di equivalenza   essendo "può essere correlato da spostamenti circolari." enumerare tutti   queste classi di equivalenza generando   esattamente un membro di ciascuna di esse.

Ad esempio, si consideri il multinsieme {0, 1, 1, 2}. Le permutazioni "0112" e "1201" sono permutazioni unici, ma quest'ultimo possono essere trovate circolare spostando la prima e viceversa. L'algoritmo desiderato non deve generare sia.

Naturalmente un approccio forza bruta è possibile: basta generare permutazioni - indipendentemente duplicazione circolare - utilizzando uno degli algoritmi di permutazione multiset e duplicazioni rigetti trovati dal confronto con i risultati precedenti. Tuttavia, questo tende ad essere inefficiente in pratica. L'algoritmo desiderato dovrebbe richiedere il minimo, se non nullo contabilità.

Le eventuali delucidazioni in questo problema è molto apprezzato.

È stato utile?

Soluzione

Sawada dell'algoritmo

Altri suggerimenti

è leggermente più facile di andare per questo fino in basso:

se A contiene solo 1 elemento, P (A) contiene anche uno permutazione. è facile vedere le stesse opere se A contiene solo 2 elementi.

Ora, supponiamo che si dispone già di tutti i P (A) per A con n elementi, e si aggiunge un elemento. si può andare in una qualsiasi delle n punti in una qualsiasi delle permutazioni in P (A).

Credo che questa idea si traduce abbastanza direttamente ad un algoritmo ricorsivo nella lingua di propria scelta, e spero che la mia spiegazione era abbastanza chiaro.

EDIT: So che tipo di ignorato il fatto che A può contenere elementi duplicati, ma ancora pensando a quella parte:)

solo come se - se è ordinato A prima di iniziare l'algoritmo di permutazione, penso che questo potrebbe eliminare i duplicati. (Ancora pensando che anche)

Per una comprensione intuitiva del problema penso che possiamo utilizzare questa metafora. Visualizzare un orologio sul muro, ma invece di avere 12 posizioni sulla faccia ha n dove n è il numero di elementi nel set.

Poi la classe di ciascuna di equivalenza è solo un incarico di un elemento di A ad una posizione sul quadrante dell'orologio.

Una volta assegnato un altro permutazione della stessa classe di equivalenza può essere generato semplicemente ruotando l'orologio sulla parete.

Per generare un'altra permutazione non correlato di A è necessario disporre di un elemento saltare almeno un altro elemento.

Ora l'algoritmo come la vedo io sarebbe quello di iniziare con un incarico ad esempio dire che abbiamo avuto quattro elementi in A = {a, b, c, d} e li abbiamo assegnato alle 12, 3, 6 e 9 posizioni rispettivamente per chiarezza visiva. Allora la nostra prima operazione potrebbe essere quella di swap a e b. poi A e C, poi A e D, allora sarebbe andato a B e scambio con l'elemento in posizione 3 che ora è c.

In questo modo finché non abbiamo raggiunto d genererebbe un rappresentante di tutte le classi di equivalenza.

Questo non significa prendersi cura di duplicati ma dovrebbe essere molto più efficiente di generare tutte le permutazioni di A.

Il pensiero che viene in mente è che per ogni set che ha almeno un elemento che appare solo una volta allora si può mettere l'elemento nella prima posizione della lista per tutte le risposte e quindi generare tutte le permutazioni del resto del i numeri. Questa è una soluzione abbastanza banale in quanto il fatto vostro primo elemento è assicura unici che non ci sono equivalenti di ciclo di spostamento degli elementi. Chiaramente poi tutte le soluzioni generate devono essere univoci.

Il problema evidente è che se non hai elementi che sono single, allora questo si rompe del tutto. Il motivo principale che ho messo questo in ragione fosse perché è ci sono diverse altre soluzioni che si occupano di non duplicati e credo che questo è più efficace di loro (Risolve più casi) in modo da è degno di menzione. La sua anche piuttosto semplice in termini di capire come funziona e la sua attuazione. Spero solo che il mio ragionamento è il suono. ; -)

Modifica per ulteriori pensieri:

Mi viene da pensare che questo principio può essere esteso alla situazione in cui si dispone di duplicati in una certa misura.

Se si prende un elemento (che assumiamo oggi si ripete) si può guardare solo le sue permutazioni e quali consentirebbero di cambiamento del ciclo di ripetizione, come prima assumign che è possibile un "blocco" in luogo senza perdita di generalità. ad esempio, se si dispone di un totale di 6 elementi e A appare due volte in questo insieme, allora si può avere:

AAXXXX, AXAXXX, AXXAXX, AXXXAX, AXXXXA

L'ultimo di questi è lo stesso del primo (entro spostamento ciclico) e quindi può essere ignorato, idem il secondo e quarto. Il terzo (AXXAXX) può essere riciclato per tre per tornare a se stesso in modo ha il potenziale per cicli. I primi due non possono mai dar luogo a cicli, non importa quante volte si pedala in modo tuttavia è distribuire i restanti elementi è necessario garantire solo che sono distribuzioni unici e si sono garantiti per ottenere unica risultati del ciclo.

Per il terzo modello che può ciclo (AXXAXX) si avrebbe bisogno di guardare elemento di B e ripetere il processo per quelli. Questa volta sfortunatamente si sarebbe in grado di utilizzare il trucco di bloccare il primo valore per risparmiare tempo.

Io non sono sicuro al 100% come si dovrebbe fare per fare questo in un programma completamente funzionante ma i suoi alcuni thougths su come evitare di dover forza bruta.

propongo qui una soluzione implementata in Python 

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]

L'idea è quella di costruire collane diverse da permutazioni dei due elementi. Per un elenco di quattro elementi a, b, c, d il algo rendimenti: 

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top