Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 10
Algoritmos para Gerar Permutações e Combinações em Ordem
Lexicográfica
Algoritmo: conjunto de instruções cuja execução, numa ordem préestabelecida, conduz à realização de uma tarefa (um cálculo,
por exemplo).
Léxico: Conjunto de palavras de uma linguagem.
Ordem Lexicográfica. Consideremos as sequências construídas com
símbolos de um dado conjunto ordenado (por exemplo,
sequências de letras do alfabeto, com a ordenação normal que
lhes está associada, primeiro o a, depois b, c, d, etc). Ordenar as
sequências por ordem lexicográfica, corresponde a ordená-las
como as palavras de um dicionário.
Exemplos
Consideremos a ordenação a < b < c < d …, das letras do
alfabeto. Podemos escrever
beta < beto,
aa < aaa [acrescentam-se espaços à direita da
palavra mais curta, de modo que as duas
fiquem com igual comprimento; o espaço
é considerado o “menor” símbolo do
alfabeto],
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 11
rita < rute
ana < anabela.
GERAR PERMUTAÇÕES POR ORDEM LEXICOGRÁFICA
Considere o seguinte problema: escrever em ordem lexicográfica
todas as permutações possíveis dos dígitos 1,2,3,4.
Representemos as permutações pelos números de quatro dígitos
que lhes correspondem: 1234, 1342, etc. Observemos o seguinte:
- o menor número que se pode escrever é 1234;
- o maior número que se pode escrever é 4321;
- percorrendo o maior número da direita para a esquerda
verificamos que cada dígito é maior que o que está à sua
direita;
- quando isto não acontece, ao percorrermos uma
permutação da direita para a esquerda, então essa
permutação não corresponde ao maior número possível.
Podemos resolver o problema do seguinte modo:
A. Escrevemos o menor número, 1234.
B. Percorremos o número da direita para a esquerda,
comparando pares sucessivos de dígitos. Se em alguma
dessas comparações o dígito da esquerda for menor que o
da direita, faz-se o seguinte, considerando apenas o
conjunto dos dígitos já comparados:
- seja p a posição do referido dígito da esquerda;
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 12
- coloca-se na posição p do dígito da esquerda o
dígito que lhe for imediatamente superior, de
entre todos os já comparados;
- os restantes elementos do conjunto dos dígitos já
comparados escrevem-se então à direita da
posição p, por ordem crescente.
C. Repete-se este algoritmo desde o passo B, até se obter o
número 4321.
[ver exemplos em vídeo]
Complete a resposta anterior: 1234, 1243, 1324, ….
Generalizando: se quisermos escrever em ordem lexicográfica
todas as permutações de n objectos distintos, o1 , o 2 ,  , o n , nos
quais está definida uma ordenação o1  o 2    o n , procedemos
do seguinte modo (si é o símbolo na posição i):
A. Percorrer a sequência s1s 2  s n da direita para a
esquerda, comparando pares de símbolos consecutivos,
até se encontrar um par de símbolos s k s k 1 tal que
s k  s k 1 (se não existir um par de símbolos nestas
condições, então terminar), e fazer o seguinte:
- trocar a posição do símbolo s k com a do menor
símbolo à sua direita que seja maior que s k ;
- ordenar em seguida, por ordem crescente, todos os
símbolos à direita da posição k; a sequência obtida é
uma permutação.
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 13
B. Repetir o passo A com a nova permutação obtida.
[ver exemplos em vídeo]
GERAR COMBINAÇÕES POR ORDEM LEXICOGRÁFICA
Considere o seguinte problema: escrever por ordem lexicográfica
todas as combinações de 3 dígitos que se podem obter com os
dígitos 1,2,3,4,5.
Representemos as combinações pelos números que se obtêm,
colocando os dígitos respectivos por ordem crescente (123, 234,
etc). Note que 123 é o menor número e 345 o maior número que é
possível obter com combinações de 3 dígitos.
Podemos resolver o problema do seguinte modo:
A. Começar com a combinação 123.
B. Depois,
- escrever todos os números que se obtêm fazendo o terceiro
símbolo (a contar da esquerda) tomar os valores de 4 até ao
máximo, que é 5:
124
125;
- uma vez obtida a combinação com o maior símbolo possível
na terceira posição, escrever na segunda posição o símbolo
imediatamente superior a 2, neste caso o 3; escrever na
terceira posição o símbolo imediatamente superior a 3,
neste caso o 4:
134,
e repetir os passo anteriores até o símbolo na segunda
posição ser 4 (não pode ser maior; porquê?):
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 14
135
145.
- escrever agora na primeira posição o símbolo 2 (que é o
símbolo imediatamente superior a 1), escrever na segunda
posição o 3 (que é o símbolo imediatamente superior a 2), e
na terceira posição o símbolo imediatamente superior a 3 (
o 4):
234
C. Repetir este algoritmo desde B, até se obter a combinação 345.
235
245
345.
Obtiveram-se as 10 combinações possíveis.
Generalizando: se quisermos escrever em ordem lexicográfica
todas as combinações r a r, de n objectos distintos, o1 , o 2 ,  , o n ,
entre os quais está definida uma ordenação o1  o 2    o n ,
procedemos do seguinte modo:
A. Começar por escrever a combinação o1 , o 2 ,  , o r ;
B. Para encontrar a combinação seguinte:
- percorrer a sequência da direita para a esquerda, até
encontrar uma posição k com um símbolo Oi < On que possa
ser substituído pelo que lhe é imediatamente superior, Oi+1;
- nesta posição, k, substitui-se o símbolo Oi pelo símbolo Oi+1;
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar
Matemática Discreta
ESTiG\IPB
Cap3. Princípios Elementares de Contagem
pg 15
- nas posições k+1, k+2, … , (a contar da esquerda), colocamse em crescendo os símbolos Oi+2, Oi+3, … , até formar uma
sequência de r símbolos;
C. Se a sequência já contiver os r maiores símbolos, então terminar.
Senão, determinar a próxima combinação executando o
algoritmo a partir do passo B com a sequência até aqui obtida.
ESTiG/IPB
Departamento de Matemática
Mário Abrantes
http://www.ipb.pt/~mar