UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
COMBINATORIAS
Esta clase cubre algoritmos combinatorios básicos los cuales generan sucesivamente todas las permutaciones, combinaciones y variaciones respectivamente. Refresca tu memoria! ¿Cuántas permutaciones, combinaciones y variaciones se pueden generar de un conjunto de N elementos? y ¿Qué pasa si los elementos repetidos son permitidos?
PERMUTACIONES
La permutación de una lista L es una lista que contiene todos los elementos de la lista L en algún orden. Adivina cual permutación es generada primero usando el siguiente procedimiento. Y ¿Qué pasa con el segundo?
perm(Lista,[H|Perm]) :-
borrar(H,Lista,Rest),perm(Rest,Perm).
perm([],[]).
borrar(X,[X|T],T).
borrar(X,[H|T],[H|NT]) :- borrar(X,T,NT).
COMBINACIONES
Una combinación es un subconjunto arbitrario del conjunto que contiene un número dado de elementos. El orden de los elementos es irrelevante.
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :- N>0,N1 is N-1,comb(N1,T,Comb).
comb(N,[_|T],Comb) :- N>0,comb(N,T,Comb).
Es posible programar un generador de combinaciones sin aritmética: el siguiente procedimiento comb2 asume que la lista con N variables libres como su segundo argumento y enlaza esas variables. Así, usar ?-comb2([1,2,3,4],[X,Y]) para generar combinaciones con dos elementos.
comb2(_,[]).
comb2([X|T],[X|Comb]) :- comb2(T,Comb).
comb2([_|T],[X|Comb]) :- comb2(T,[X|Comb]).
COMBINACIONES CON ELEMENTOS REPETIDOS
Este tipo de combinación puede contener un elemento más veces. Así, éste no es un conjunto sino un multiconjunto.
comb_rep(0,_,[]).
comb_rep(N,[X|T],[X|RComb]) :-
N>0,N1 is N-1,comb_rep(N1,[X|T],RComb).
comb_rep(N,[_|T],RComb) :- N>0,comb_rep(N,T,RComb).
Intenta programar combinaciones con elementos repetidos también como algoritmos combinatoriales sin aritmética, es decir, sin contador numérico.
VARIACIONES
Una variación es un subconjunto con un número dado de elementos. El orden de los elementos en la variación es importante.
varia(0,_,[]).
varia(N,L,[H|Varia]) :- N>0,N1 is N -1,
borrar(H,L,Rest),varia(N1,Rest,Varia).
VARIACIONES CON ELEMENTOS REPETIDOS
Otra vez, este tipo de variación puede contener elementos repetidos.
varia_rep(0,_,[]).
varia_rep(N,L,[H|RVaria]) :-
N>0,N1 is N-1,borrar(H,L,_),varia_rep(N1,L,RVaria).
Las combinatorias, permutaciones y variaciones son poderosas para expresar la complejidad de un algoritmo pero no las incorpore en sus programas.