Problema nella comprensione dell'algoritmo di TAOCP "Molteplici permutazioni in forma di ciclo"

Question

Problema nella comprensione dell'algoritmo di TAOCP "Molteplici permutazioni in forma di ciclo"

#1 da (2 voti)

5

Non sono in grado di comprendere un algoritmo discusso nel TAOCP Volume 1; La sezione 1.3.3 denominata "Algorithm A" è stata definita "Moltiplicazioni delle permutazioni in forma ciclica", mentre è stata confrontata con l'esempio indicato nella pagina successiva.

Il passo che non è chiaro è menzionato nelle file 8th e 9th; come può essere il valore "CURRENT" diventa "g" dopo l'iterazione precedente in cui il valore CURRENT era "d"?

Si prega di fare riferimento a "The Art of Computer Programming Volume 1" di Knuth per ulteriori dettagli (sezione 1.3.3). Contiene la descrizione dettagliata di questo algoritmo.

Algoritmo dettagliato:

Algoritmo A (Molteplici permutazioni in forma di ciclo).

Questo algoritmo prende un prodotto di cicli, come (6), e calcola la permutazione risultante in forma di un prodotto di cicli disgiunti. Per semplicità, la rimozione dei cicli singleton non è descritto qui; sarebbe un'estensione abbastanza semplice dell'algoritmo. Mentre questo algoritmo viene eseguito, successivamente "taggano" gli elementi dell'input formula; cioè, contrassegniamo in qualche modo quei simboli della formula di input che hanno stato elaborato.

A1. [Primo passaggio.] Contrassegna tutte le parentesi e sostituisci ciascuna parentesi destra con una copia taggata dell'elemento che segue la parentesi sinistra corrispondente. (Vedere l'esempio nella Tabella 1.)
A2. [Apri.] Cercando da sinistra a destra, trova il primo elemento senza tag del ingresso. (Se tutti gli elementi sono taggati, l'algoritmo termina.) Imposta START uguale ad esso; mostra una parentesi chiusa; emettere l'elemento; e taggalo.
A3. [Vedi CORRENTE.] Imposta CORRENTE uguale all'elemento successivo della formula.
A4. [Formula di scansione.] Procedere a destra fino a raggiungere la fine del formula, o trovare un elemento uguale a CORRENTE; in quest'ultimo caso, taggalo e tornare al punto A3.
A5. [CURRENT = START?] Se CURRENT i- START, invia CURRENT e torna a passo A4 ricominciare a sinistra della formula (continuando così il sviluppo di un ciclo nell'output).
A6. [Chiudi.] (È stato trovato un ciclo completo nell'output.) Emettere a destra parentesi e tornare al punto A2.

algorithms taocp

posta user100202 21.08.2013 - 21:29

fonte

1 risposta

Leggi altre domande sui tag algorithms taocp

OOP, modelli di dominio e utente Quali concetti sono pertinenti per pianificare una strategia di "documentazione per l'utente finale"?

score 2 · Answer 1

Nella mia copia del libro, la riga # 7 ha valore CURRENT d , la riga # 8 ha valore CURRENT g e la riga # 9 ha valore CURRENT a . Immagino quindi che tu sia confuso riguardo alla transizione tra le righe 7 e 8, che sono le seguenti:

Row #  After step no.  START  CURRENT  ( a c f g a ( b c d b ( a e d a ( f a d e f ( b g f a e b  Output
  #7        A5           a       d     x x       x x   x   x x     x x x   x     x x           x    d
  #8        A5           a       g     x x       x x   x x x x     x x x   x     x x x         x    g

La riga n. 8 inizia con lo stato descritto nella riga n. 7 ed esegue il passaggio A5, che riporta il cursore all'inizio dell'elenco e torna al passaggio A4. Qui, il passaggio A4 viene eseguito tre volte:

Continua finché non raggiunge un d ; etichetta d perché è uguale a CURRENT; imposta CURRENT uguale a b , perché b viene dopo questo particolare d .
Continua finché non raggiunge un altro b ; etichetta b perché è uguale a CURRENT; imposta CURRENT uguale a g , perché g viene dopo questo particolare b .
Continua finché non raggiunge la fine degli elementi, perché non trova un altro g .

Puoi vedere i nuovi tag d e b se confronti le righe 7 e 8. In particolare, la seconda iterazione del passo A4 all'interno del passo A5 della riga # 8 è ciò che fa sì che CURRENT sia impostato su g .