Part of INTERACTIVE PROLOG GUIDE | Prev | TOC | Next |
This lecture covers basic combinatorial algorithms which generate successively all permutations, combinations and variations respectively. Refresh your memory! How many permutations, combinations and variations can be generated from set of N elements? And what about if repeated elements are allowed?
Permutation of the list L is a list containing all elements of list L in some order. Guess which permutation is generated first usign following procedure. And what about second?
perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm). perm([],[]). delete(X,[X|T],T). delete(X,[H|T],[H|NT]):-delete(X,T,NT).
Combination is an arbitrary subset of the set containing given number of elements. The order of elements is irrelevant.
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).
It is possible to program generator of combinations without arithmetics. The following procedure comb2 assumes the list with N free variables as its second argument and it binds these variables. So, use ?-comb2([1,2,3,4],[X,Y]) to generate combinations with two elements.
comb2(_,[]). comb2([X|T],[X|Comb]):-comb2(T,Comb). comb2([_|T],[X|Comb]):-comb2(T,[X|Comb]).
This type of combination can contain an element more times. Thus, it is not a set but a multi-set.
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).
Try to program combinations with repeted elements as well as followingcombinatorial algorithms without aritmetics, i.e., without numerical counter.
Variation is a subset with given number of elements. The order of elements in variation is significant.
varia(0,_,[]). varia(N,L,[H|Varia]):-N>0,N1 is N-1,delete(H,L,Rest),varia(N1,Rest,Varia).
Again, this type of variation can contain repeated elements.
varia_rep(0,_,[]). varia_rep(N,L,[H|RVaria]):-N>0,N1 is N-1,delete(H,L,_),varia_rep(N1,L,RVaria).
Part of INTERACTIVE PROLOG GUIDE | Prev | TOC | Next |