Backtracking
Animação dos Algoritmos de
Permutação, Geração de Subconjuntos e
Soma de Subconjuntos
Paulo Eustáquio Duarte Pinto
(pauloedp arroba ime.uerj.br)
abril/2005
Backtracking
Geração de Permutações - Versão 2
Listar todas as n! permutações de um conjunto
Perm:
Fim;
Para i de 1 a n:
Se (not S[i]) Então
np  np + 1; P[np]  i;
Se (np = n) Então
Imprime
Senão
Perm;
np  np - 1; S[i]  F;
Fp;
Externamente:
S  F;
np  0;
Perm;
S[i]  V;
Backtracking
n=3
{}
i=1
{1}
i = 1 ,2
{1,2}
i = 1 ,2,3
- Geração de Permutações
Backtracking
n=3
{}
i=1
{1}
i = 1 ,2
{1,2,3}
i = 1 ,2,3
- Geração de Permutações
123
Backtracking
n=3
{}
i=1
{1}
i = 1 ,2 ,3
{1,2}
i = 1 ,2,3
{1,3}
i = 1 ,2
- Geração de Permutações
123
Backtracking
n=3
{}
i=1
{1}
i = 1 ,2 ,3
{1,2}
i = 1 ,2,3
{1,3,2}
i = 1 ,2
- Geração de Permutações
123
132
Backtracking
- Geração de Permutações
n=3
{}
i = 1 ,2,3
{1}
i = 1 ,2 ,3
{1,2}
i = 1 ,2,3
{1,3}
i = 1 ,2,3
{2}
i = 1,2 ,3
{2,1}
i = 1,2,3
{3}
i = 1,2 ,3
{2,3}
i = 1 ,2,3
123
132
213
231
312
321
{3,1}
{3,2}
i = 1 ,2,3 i = 1,2,3
.
Backtracking
Geração de Subconjuntos
Número de subconjuntos de C = {c1... cn} = 2n
GeraSub (p):
Para i de p a n:
ns  ns + 1; S[ns]  i;
Imprime;
Se (i < n) Então
GeraSub (i + 1);
ns  ns - 1;
Fp;
Fim;
Externamente:
ns  0; GeraSub (1);
Backtracking
- Geração de Subconjuntos
C = {a, b, c, d}
1
{}
i = 1 ,2,3,4
2
{1}
{2}
i = 3,4
i = 2 ,3,4
{1, 2}
i = 3 ,4
3
{1, 2, 3}
4
i=4
.
{1, 3}
i=4
4
3
{2, 3}
i=4
{3}
i=4
4
4
{1}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,4}
{1,3}
{1,3,4}
{1,4}
{2}
{2,3}
{2,3,4}
{2,4}
{3}
{3,4}
{4}
Backtracking
Geração de Subconjuntos
Subconjuntos gerados para:
{
{
{
{
{
{
{
{
a },
a, b },
a, b, c },
a, b, c, d },
a, b, d },
a, c },
a, c, d },
a, d },
{ a, b, c, d }
{
{
{
{
{
{
{
b },
b, c },
b, c, d },
b, d },
c },
c, d },
d }
Backtracking
- Soma de Subconjuntos
SomaSub (pi):
i  pi;
Enquanto (i  n) e ((soma + C[i])  s):
ns  ns + 1; S[ns]  i; soma  soma + C[i];
Se (soma = s) Então
Imprime
Senão
SomaSub (i+1);
ns  ns - 1; soma  soma - C[i];
i  i + 1;
Fe;
Fim;
Externamente: ns  0; s  0; Ordena C;
SomaSub (1);
Backtracking
- Soma de Subconjuntos
C = {1, 2, 2, 3, 4, 5, 9}, s = 4
{}
1
i = 1 ,2,3,4,5,6
{1}
2
i = 2 ,3,4 ,5
{1, 2}
i=3
1, 3
2, 2
4
.
3
3
{2}
i = 3 ,4
{1, 2}
i=4
{2}
i=4
4
4
{3}
i=5
5