; repeat (∗ repete ate conseguir construir uma permutacao valida ∗) for i := 1 to n do v[ i ]:= random (n) + 1; (∗ sorteia numero entre 1 e n ∗) until testa permutacao (v, n) ; end; (∗ gera permutacao1 ∗) Figura 10.28: Gerando uma permutac¸a˜o, versa˜o 1. didade de se aproveitar func¸o˜es ja´ existentes, este mesmo autor pensou que poderia gerar o vetor de modo diferente: gerar um a um os elementos e testar se eles ja´ na˜o pertencem ao conjunto ja´ gerado ate´ a iterac¸a˜o anterior. Isto garante que o vetor final produzido e´ va´lido. A procedure da figura 10.29 apresenta a implementac¸a˜o desta nova ideia. procedure gerar permutacao2 (var v: vetor i ; var n: integer) ; var i , j : integer ; begin read (n) ; randomize ; v[1]:= random (n) + 1; for i := 2 to n do repeat v[ i ]:= random (n) + 1; (∗ gera um numero entre 1 e n ∗) j:= 1; (∗ procura se o elemento ja existe no vetor ∗) while ( j < i ) and (v[ i ] <> v[ j ] ) do j:= j + 1; until j = i ; (∗ descobre que o elemento eh novo ∗) end; (∗ gera permutacao2 ∗) Figura 10.29: Gerando uma permutac¸a˜o, versa˜o 2. Este algoritmo executa na casa de 2 segundos para vetores de tamanho pro´ximos de 1000, mas demora cerca de 30 segundos para entradas de tamanho que beiram os 30.000. Para se pensar em tamanhos maiores a chance do tempo ficar insuporta´vel e´ enorme. Mas ja´ e´ melhor do que o anterior. Queremos gerar um vetor que represente uma permutac¸a˜o, provavelmente para fins de testes. Uma maneira poss´ıvel seria a seguinte: inicializa-se um vetor de forma ordenada, depois faz-se alterac¸o˜es aleato´rias de seus elementos um nu´mero tambe´m aleato´rio de vezes. Esta ideia foi implementada e e´ mostrada na figura 10.30. Este co´digo produz corretamente vetores que representam permutac¸o˜es com bom grau de mistura dos nu´meros em tempo praticamente constante para entradas da 156 CAPI´TULO 10. ESTRUTURAS DE DADOS procedure gerar permutacao3 (var v: vetor i ; var n: integer) ; var i , j , k, aux, max: integer ; begin read (n) ; randomize ; for i := 1 to n do v[ i ] := i ; max:= random (1000) ; (∗ vai trocar dois elementos de 0 a 999 vezes ∗) for i := 1 to max do begin j:= random (n) + 1; k:= random (n) + 1; aux:= v[ j ] ; v[ j ]:= v[k ] ; v[k]:= aux; end; end; (∗ gera permutacao3 ∗) Figura 10.30: Gerando uma permutac¸a˜o, versa˜o 3. ordem de um milha˜o de elementos (usando-se o tipo longint).7 Em uma aula do segundo semestre de 2010 surgiu uma nova ideia para se gerar um vetor de permutac¸a˜o.8 A sugesta˜o e´ modificar o algoritmo 10.29, fazendo com que um vetor auxiliar contenha os nu´meros ainda na˜o colocados no vetor permutac¸a˜o. O sorteio deixa de ser sobre o elemento a ser inserido, mas agora sobre o ı´ndice do vetor auxiliar, cujo tamanho decresce na medida em que os nu´meros va˜o sendo sorteados. O co´digo da figura 10.31 ilustra estas ideias. Ele foi implementado durante a aula e possibilitou gerar vetores de tamanhos incrivelmente grandes em tempo extremamente curto.9 Determinando a ordem de uma permutac¸a˜o Antes de apresentarmos o pro´ximo problema do ponto de vista algoritmico a ser tratado precisamos introduzi-lo do ponto de vista matema´tico. Observem que, uma vez que a func¸a˜o que define a permutac¸a˜o e´ sobre o pro´prio conjunto, ocorre que, se P (n) e´ uma permutac¸a˜o, enta˜o P (P (n)) tambe´m e´. Logo, e´ poss´ıvel calcular o valor de expresso˜es tais como P (P (1)). De fato, consideremos novamente a permutac¸a˜o: ( 1 2 3 4 5 4 1 5 2 3 ) 7Se algue´m souber de um modo mais eficiente de gerar uma permutac¸a˜o, favor avisar. Na˜o so´ daremos os cre´ditos necessa´rios como tambe´m mostraremos os resultados aqui neste material. 8Cre´ditos para o Felipe Z. do Nascimento. 9Co´digo e testes feitos na aula por Renan Vedovato Traba, a partir da ideia do Felipe. 10.1. VETORES 157 procedure gera aux(var aux: vetor i ; var tam : longint) ; var i : longint ; begin for i := 0 to tam do aux[ i ] := i ; end; procedure gerar permutacao4 (var v: vetor ; var n: longint) ; var i , j : longint ; begin read (n) ; randomize ; tam:= n; for i := 0 to n do begin j := random(tam+1); p[ i ] := aux[ j ] ; aux[ j ] := aux[tam] ; tam := tam−1; end; end; (∗ gera permutacao4 ∗) Figura 10.31: Gerando uma permutac¸a˜o, versa˜o 4. Enta˜o pode-se calcular: • P (P (1)) = P (4) = 2. • P (P (2)) = P (1) = 4. • P (P (3)) = P (5) = 3. • P (P (4)) = P (2) = 1. • P (P (5)) = P (3) = 5. Desta maneira, definimos P 2(n) = P (P (n)). Em termos gerais, podemos definir o seguinte: { P 1(n) = P (n); P k(n) = P (P k−1(n)) k ≥ 2. Dentre todas as permutac¸o˜es, existe uma especial: ID = ( 1 2 3 4 5 1 2 3 4 5 ) Isto e´, P (i) = i,∀i. Esta permutac¸a˜o recebe um nome especial ID. E´ poss´ıvel de- monstrar que, para quaisquer k e n, IDk(n) = ID(n). Tambe´m e´ poss´ıvel demonstrar que a sentenc¸a seguinte tambe´m e´ va´lida: 158 CAPI´TULO 10. ESTRUTURAS DE DADOS Seja P (n) uma permutac¸a˜o sobre um conjunto de n elementos. Enta˜o existe um nu´mero natural k tal que P k = ID. Este nu´mero natural e´ chamado da ordem da permutac¸a˜o. Vamos considerar como exemplo a permutac¸a˜o acima. Podemos calcular para valores pequenos de k como e´ P k: P = ( 1 2 3 4 5 4 1 5 2 3 ) P 2 = ( 1 2 3 4 5 2 4 3 1 5 ) P 3 = ( 1 2 3 4 5 1 2 5 4 3 ) P 4 = ( 1 2 3 4 5 4 1 3 2 5 ) P 5 = ( 1 2 3 4 5 2 4 5 1 3 ) P 6 = ( 1 2 3 4 5 1 2 3 4 5 ) Isto e´, a ordem da permutac¸a˜o P e´ 6. Chegamos no ponto de apresentarmos o pro´ximo problema10. Dada uma per- mutac¸a˜o, encontrar sua ordem. Simular a sequeˆncia de operac¸o˜es e testar quando a identidade for encontrada, contando quantas operac¸o˜es foram feitas e´ muito caro. Tem que haver uma maneira melhor. A func¸a˜o da figura 10.32 implementa um algoritmo que recebe como entrada uma permutac¸a˜o (va´lida) e retorna sua ordem. Este algoritmo parte da ideia de que cada elemento P (i) = x do conjunto re- torna a` posic¸a˜o i ciclicamente, de cont em cont permutac¸o˜es. Ou seja, P cont(i) = x, P 2×cont(i) = x, . . .. O mesmo ocorre para todos elementos do conjunto, mas cada um possui um ciclo (valor de cont) pro´prio. Para exemplificar, tomemos a permutac¸a˜o acima. Para o ı´ndice 1, temos que P 3(1) = 1. Isto quer dizer que para todo mu´ltiplo de 3 (a cada 3 iterac¸o˜es) e´ verdade que P 3k(1) = 1. Isto tambe´m ocorre para os ı´ndices 2 e 4. Mas para os ı´ndices 3 e 5, o nu´mero de iterac¸o˜es para que ocorra uma repetic¸a˜o e´ de duas iterac¸o˜es. Logo, pode- se concluir que a permutac¸a˜o ID ocorrera´ exatamente na iterac¸a˜o que e´ o mı´nimo mu´ltiplo comum (MMC) entre o nu´mero que provoca repetic¸a˜o entre todos os ı´ndices. Observamos que: MMC(x1, x2, . . . , xn) = MMC(x1,MMC(x2, . . . , xn). Infelizmente, na˜o existe algoritmo eficiente para ca´lculo do MMC. Mas existe para o ca´lculo do MDC (ma´ximo divisor comum). De fato, implementamos o algoritmo de 10Este e´ o problema da Maratona da ACM. 10.1. VETORES 159 function ordem permutacao (var v: vetor i ; n: integer) : int64 ; var mmc, cont : int64 ; p, i : integer ; begin mmc := 1; for i := 1 to n do begin cont := 1; p := i ; while (v[p] <> i ) do begin cont:= cont + 1; p := v[p ] ; end; writeln (cont) ; mmc := mmc ∗ cont div mdc(mmc, cont) ; end; ordem permutacao:= mmc; end. Figura 10.32: Calcula a ordem de uma permutac¸a˜o. Euclides (figura 6.16, sec¸a˜o 6.4) e mostramos que ele e´ muito eficiente. Felizmente, a seguinte propriedade e´ verdadeira: MDC(a, b) = a× b MMC(a, b) O programa acima explora este fato e torna o co´digo muito eficiente para calcular a ordem de permutac¸o˜es para grandes valores de n. O estudante e´ encorajado aqui a gerar uma permutac¸a˜o com os algoritmos estudados nesta sec¸a˜o e rodar o programa para valores