Backtracking: Permutação, Subconjuntos e Soma

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
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:
	Para i de 1 a n:
		Se (not S[i]) Então
			 np  np + 1; P[np]  i; S[i]  V; 
			Se (np = n) Então
				Imprime
			Senão
				Perm;
			np  np - 1; S[i]  F; 
	Fp; 
Fim;
Externamente:
 	S  F; np  0; Perm;
*
*
*
Backtracking - Geração de Permutações 
i = 1 
n = 3
i = 1 
,2
i = 1 
,2
,3
*
*
*
Backtracking - Geração de Permutações 
i = 1 
n = 3
i = 1 
,2
{1,2,3}
i = 1 
,2
,3
1 2 3
*
*
*
Backtracking - Geração de Permutações 
i = 1 
n = 3
i = 1 
,2
{1,2}
i = 1 
,2
,3
1 2 3
,3
i = 1 
,2
*
*
*
Backtracking - Geração de Permutações 
i = 1 
n = 3
i = 1 
,2
{1,2}
i = 1 
,2
,3
1 2 3
,3
i = 1 
,2
1 3 2
*
*
*
Backtracking - Geração de Permutações 
i = 1 
n = 3
i = 1 
,2
{1,2}
i = 1 
,2
,3
1 2 3
,3
i = 1 
,2
1 3 2
,3
,2
i = 1 
i = 1 
,2
,3
2 1 3
,2
,3
i = 1 
,2
,3
2 3 1
,3
i = 1 
i = 1 
,2
3 1 2
,3
,2
i = 1 
3 2 1
,2
,3
,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;
		GeraSub (i + 1);
		ns  ns - 1;
	Fp; 
Fim;
Externamente:
 	ns  0;
	GeraSub (1);
*
*
*
Backtracking - Geração de Subconjuntos 
i = 1 
i = 2 
i = 3 
i = 4 
,3
,4
i = 3 
,4
,2
,3
,4
i = 4 
C = {a, b, c, d}
.
i = 4 
i = 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, b, c, d }
 	{ a },				{ b },
	{ a, b },				{ b, c },
	{ a, b, c },			{ b, c, d },
	{ a, b, c, d },			{ b, d },
	{ a, b, d },			{ c },
	{ a, c },				{ c, d },
	{ a, c, d },			{ d }
	{ a, 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 
i = 1 
i = 2 
i = 3 
i = 4 
,3
,4
,5
1, 3
i = 3 
,4
2, 2
,2
,3
,5
,6
,4
4
i = 4 
i = 5 
C = {1, 2, 2, 3, 4, 5, 9}, s = 4
.