apostila

;
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