Semplificazione ottimale dei prodotti di trasposizione

Question

Semplificazione ottimale dei prodotti di trasposizione

#1 da (0 voti)

2

Sto cercando di prendere un prodotto di un gran numero di trasposizioni e di ridurlo a un numero inferiore di prodotti. Ho il seguente codice e vorrei qualche input sui modi efficienti per far bollire questi prodotti. Prima di fornire il codice, è importante riconoscere quanto segue:

Le trasposizioni, una permutazione ciclica di due elementi, hanno le seguenti proprietà:

Il prodotto di trasposizioni identiche si annulla. Ad esempio, (1,2) (1,2) (2,3) = (2,3).
Qualsiasi prodotto del modulo (x, y) (y, z) (x, y) è uguale a (y, z) (x, y) (y, z).
Tutte le trasposizioni che non condividono elementi commutano. Cioè, (u, v) (x, y) = (x, y) (u, v).

Il codice che ho è sotto. Questa è una procedura che ottiene un input di una lista che contiene un numero di tuple di 2 che rappresentano le trasposizioni. Ad esempio, l'input valido è [(1,2) (2,3) (1,2)]. Ho una piccola spiegazione in fondo al codice indicato.

count = 1
while count != 0:
    count = 0
    repeatCount = 0
    swappedCount = 0
    for i in range(len(route)-1):
        if len(route) > 1 and repeatCount == 0:
            if route[i] == route[i+1]:
                route.pop(i+1)
                route.pop(i)
                count += 1
                repeatCount += 1

    for i in range(len(route)-3):
        if len(route) > 3 and swappedCount == 0:
            if route[i] == route[i+2] and route[i+1] == route[i+3]:
                route.pop(i+3)
                route.pop(i+2)
                route.insert(i,route[i+1])
                route.pop(i+2)
                count += 1
                swappedCount += 1

Il primo per le ricerche di ciclo delle istanze di proprietà (1) sopra e il secondo per la ricerca del ciclo per le istanze di proprietà (2). I contatori repeatCounter e swappedCounter sono il mio tentativo grossolano di evitare un IndexError.

Qualsiasi modo per ottenere questo risultato completo, ossia essere sempre in grado di ridurre qualsiasi prodotto al minimo assoluto, in un modo tempestivo sarebbe molto apprezzato, poiché il tempo di esecuzione è un problema per il resto dell'intero programma.

Per chiarimenti, spiegherò alcuni dei contesti in cui appare questo problema. Considera un grafico G con vertici etichettati. Su ogni vertice si trova un ciottolo, p-i. Una trasposizione nel prodotto dato corrisponde alla selezione di un bordo in G e allo scambio dei ciottoli che sono incidenti su quel bordo.

Pertanto, un prodotto di trasposizioni corrisponde a un processo di scambio di ciottoli di bordi e il risultato finale è una permutazione dei ciottoli su G che è descritta dalla permutazione data dal prodotto delle trasposizioni.

Quindi, questo processo di far bollire un prodotto di trasposizioni è un tentativo di ridurre il numero di scambi necessari per ottenere una permutazione di ciottoli su un grafico G.

performance python algorithms optimization

posta Santana Afton 02.06.2016 - 07:32

fonte

1 risposta

Leggi altre domande sui tag performance python algorithms optimization

Gradle Flavors vs. App Projects Ci sono aspetti negativi nella scrittura di istruzioni PDO / mysqli nel mio codice direttamente vs utilizzando i miei metodi di wrapper di reindirizzamento?

score 0 · Answer 1

Avrei pensato che sarebbe stato più semplice calcolare la composizione di tutte le permutazioni e poi provare a ridurlo di nuovo. Non so se sarà ottimale, ma immagino che le regole di cui parli siano il tipo di cosa che si annullerebbe quando moltiplichi le permutazioni. In questo approccio, fondamentalmente, si vogliono due funzioni: una per moltiplicarsi (si spera che ne consegua una cancellazione) e un'altra per ricondurla alle trasposizioni. Nel tuo esempio

(1,2)(2,3)(1,2) -> (2,3)

Moltiplicare dà una trasposizione che è chiaramente ottimale per questa permutazione.

Ecco un codice per moltiplicare le permutazioni. Il codice li converte in dict e quindi moltiplica le permutazioni dict e semplifica le parti degli swap ridondanti:

def to_dict(p):
    d = {p[i]: p[i+1] for i in range(len(p)-1)}
    d[p[-1]] = p[0]
    return d

def perm_prod2(d1, d2):
    keys = d1.keys() | d2.keys()
    d3 = {}
    for n in keys:
        newn = n
        newn = d2.get(newn, newn)
        newn = d1.get(newn, newn)
        if n != newn:
            d3[n] = newn
    return d3

def perm_prodn(ps):
    ds = [to_dict(p) for p in ps]
    d = ds[0]
    for di in ds[1:]:
        d = perm_prod2(d, di)
    return d

print(perm_prodn([(1, 2),(1, 2), (2, 3)]))

Questo ti dà:

{2: 3, 3: 2}

che è la rappresentazione dict per

(2, 3)

Per finire, hai solo bisogno di un codice che possa trasformare il codice in un prodotto di trasposizione. È semplice dividerlo in cicli e quindi ogni ciclo può essere fattorizzato in trasposizioni come descritto qui .