apostila

;
repeat (\u2217 repete ate conseguir construir uma permutacao valida \u2217)
for i := 1 to n do
v[ i ]:= random (n) + 1; (\u2217 sorteia numero entre 1 e n \u2217)
until testa permutacao (v, n) ;
end; (\u2217 gera permutacao1 \u2217)
Figura 10.28: Gerando uma permutac¸a\u2dco, versa\u2dco 1.
didade de se aproveitar func¸o\u2dces 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\u2dco
pertencem ao conjunto ja´ gerado ate´ a iterac¸a\u2dco anterior. Isto garante que o vetor final
produzido e´ va´lido. A procedure da figura 10.29 apresenta a implementac¸a\u2dco 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; (\u2217 gera um numero entre 1 e n \u2217)
j:= 1; (\u2217 procura se o elemento ja existe no vetor \u2217)
while ( j < i ) and (v[ i ] <> v[ j ] ) do
j:= j + 1;
until j = i ; (\u2217 descobre que o elemento eh novo \u2217)
end; (\u2217 gera permutacao2 \u2217)
Figura 10.29: Gerando uma permutac¸a\u2dco, versa\u2dco 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\u2dco, provavelmente para
fins de testes. Uma maneira poss´\u131vel seria a seguinte: inicializa-se um vetor de forma
ordenada, depois faz-se alterac¸o\u2dces 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\u2dces 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) ; (\u2217 vai trocar dois elementos de 0 a 999 vezes \u2217)
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; (\u2217 gera permutacao3 \u2217)
Figura 10.30: Gerando uma permutac¸a\u2dco, versa\u2dco 3.
ordem de um milha\u2dco 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\u2dco.8
A sugesta\u2dco e´ modificar o algoritmo 10.29, fazendo com que um vetor auxiliar
contenha os nu´meros ainda na\u2dco colocados no vetor permutac¸a\u2dco. O sorteio deixa de
ser sobre o elemento a ser inserido, mas agora sobre o \u131´ndice do vetor auxiliar, cujo
tamanho decresce na medida em que os nu´meros va\u2dco 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\u2dco
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\u2dco que define a permutac¸a\u2dco e´ sobre o pro´prio
conjunto, ocorre que, se P (n) e´ uma permutac¸a\u2dco, enta\u2dco P (P (n)) tambe´m e´. Logo,
e´ poss´\u131vel calcular o valor de expresso\u2dces tais como P (P (1)). De fato, consideremos
novamente a permutac¸a\u2dco: (
1 2 3 4 5
4 1 5 2 3
)
7Se algue´m souber de um modo mais eficiente de gerar uma permutac¸a\u2dco, favor avisar. Na\u2dco 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\u22121;
end;
end; (\u2217 gera permutacao4 \u2217)
Figura 10.31: Gerando uma permutac¸a\u2dco, versa\u2dco 4.
Enta\u2dco pode-se calcular:
\u2022 P (P (1)) = P (4) = 2.
\u2022 P (P (2)) = P (1) = 4.
\u2022 P (P (3)) = P (5) = 3.
\u2022 P (P (4)) = P (2) = 1.
\u2022 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\u22121(n)) k \u2265 2.
Dentre todas as permutac¸o\u2dces, existe uma especial:
ID =
(
1 2 3 4 5
1 2 3 4 5
)
Isto e´, P (i) = i,\u2200i. Esta permutac¸a\u2dco recebe um nome especial ID. E´ poss´\u131vel de-
monstrar que, para quaisquer k e n, IDk(n) = ID(n). Tambe´m e´ poss´\u131vel demonstrar
que a sentenc¸a seguinte tambe´m e´ va´lida:
158 CAPI´TULO 10. ESTRUTURAS DE DADOS
Seja P (n) uma permutac¸a\u2dco sobre um conjunto de n elementos. Enta\u2dco existe um
nu´mero natural k tal que P k = ID. Este nu´mero natural e´ chamado da ordem da
permutac¸a\u2dco.
Vamos considerar como exemplo a permutac¸a\u2dco 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\u2dco P e´ 6.
Chegamos no ponto de apresentarmos o pro´ximo problema10. Dada uma per-
mutac¸a\u2dco, encontrar sua ordem. Simular a seque\u2c6ncia de operac¸o\u2dces e testar quando
a identidade for encontrada, contando quantas operac¸o\u2dces foram feitas e´ muito caro.
Tem que haver uma maneira melhor.
A func¸a\u2dco da figura 10.32 implementa um algoritmo que recebe como entrada uma
permutac¸a\u2dco (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\u2dco i ciclicamente, de cont em cont permutac¸o\u2dces. 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\u2dco acima. Para o \u131´ndice 1, temos que
P 3(1) = 1. Isto quer dizer que para todo mu´ltiplo de 3 (a cada 3 iterac¸o\u2dces) e´ verdade
que P 3k(1) = 1. Isto tambe´m ocorre para os \u131´ndices 2 e 4. Mas para os \u131´ndices 3 e 5, o
nu´mero de iterac¸o\u2dces para que ocorra uma repetic¸a\u2dco e´ de duas iterac¸o\u2dces. Logo, pode-
se concluir que a permutac¸a\u2dco ID ocorrera´ exatamente na iterac¸a\u2dco que e´ o m\u131´nimo
mu´ltiplo comum (MMC) entre o nu´mero que provoca repetic¸a\u2dco entre todos os \u131´ndices.
Observamos que:
MMC(x1, x2, . . . , xn) = MMC(x1,MMC(x2, . . . , xn).
Infelizmente, na\u2dco 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 \u2217 cont div mdc(mmc, cont) ;
end;
ordem permutacao:= mmc;
end.
Figura 10.32: Calcula a ordem de uma permutac¸a\u2dco.
Euclides (figura 6.16, sec¸a\u2dco 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\u2dces para grandes valores de n. O estudante e´ encorajado aqui a
gerar uma permutac¸a\u2dco com os algoritmos estudados nesta sec¸a\u2dco e rodar o programa
para valores