Problema no entendimento do algoritmo do TAOCP “Multiplicar permutações na forma de ciclo”

5

Eu não consigo entender um algoritmo discutido no Volume 1 do TAOCP; Seção 1.3.3, denominada "Algoritmo A", declarada como "Multiplicar permutações em forma de ciclo", em comparação com o exemplo indicado na próxima página.

O passo que não é claro é mencionado na 8ª e na 9ª linhas; como pode o valor "CURRENT" se tornar "g" após a iteração anterior, em que o valor CURRENT era "d"?

Por favor, consulte "A Arte do Programa de Computador Volume 1" por Knuth para mais detalhes (seção 1.3.3). Ele contém a descrição detalhada desse algoritmo.

Algoritmo detalhado:

Algoritmo A (Multiplicar permutações na forma de ciclo).

Esse algoritmo usa um produto de ciclos, como (6), e calcula a permutação resultante no forma de um produto de ciclos separados. Para simplificar, a remoção de ciclos singleton não é descrito aqui; isso seria uma extensão bastante simples do algoritmo. Como este algoritmo é executado, nós "etiquetamos" sucessivamente os elementos da entrada Fórmula; isto é, marcamos de alguma forma os símbolos da fórmula de entrada que têm processado.

  • A1. [Primeira passagem.] Identifique todos os parênteses esquerdos e substitua cada parêntese direito por uma cópia marcada do elemento que segue o parêntese esquerdo correspondente. (Vejo o exemplo na Tabela 1.)
  • A2. [Open.] Procurando da esquerda para a direita, encontre o primeiro elemento não marcado do entrada. (Se todos os elementos estiverem marcados, o algoritmo termina). igual a ele; saída um parêntese esquerdo; saída do elemento; e etiquete-o.
  • A3. [Veja CURRENT.] Defina CURRENT igual ao próximo elemento da fórmula.
  • A4. [Fórmula de digitalização.] Continue para a direita até chegar ao fim do fórmula, ou encontrar um elemento igual a CURRENT; no último caso, marque e volte ao passo A3.
  • A5. [CURRENT = START?] Se CURRENT i-START, a saída CURRENT e voltar para passo A4 iniciar novamente à esquerda da fórmula (continuando assim a desenvolvimento de um ciclo na saída).
  • A6. [Fechar.] (Foi encontrado um ciclo completo na saída). parênteses, e volte ao passo A2.
por user100202 21.08.2013 / 21:29
fonte

1 resposta

2

Na minha cópia do livro, a Linha 7 tem o valor CURRENT d , a Linha nº 8 tem o valor CURRENT g e a Linha nº 9 tem o valor CURRENT um . Portanto, presumo que você esteja confuso sobre a transição entre as linhas 7 e 8, que são as seguintes:

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

A linha nº8 começa com o estado descrito na linha nº7 e executa o passo A5, que move o cursor de volta ao início da lista e retorna ao passo A4. Aqui, o passo A4 é realizado três vezes:

  1. Continua até atingir d ; marca o d porque é igual a CURRENT; define CURRENT igual a b , porque b vem depois deste d específico.
  2. Continua até atingir outro b ; marca o b porque é igual a CURRENT; define CURRENT igual a g , porque g vem depois deste b específico.
  3. Continua até atingir o final dos elementos, porque não encontra outro g .

Você pode ver os d e b recém-marcados se comparar as linhas 7 e 8. Em particular, a segunda iteração do Passo A4 no Passo A5 da Linha nº 8 é o que faz com que CURRENT seja definido como g .

    
por 02.09.2013 / 18:49
fonte