Guide to Prolog Programming 
© Roman Barták, 1998 
Home 

Combinatorics

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,[HPerm]):delete(H,List,Rest),perm(Rest,Perm). perm([],[]). delete(X,[XT],T). delete(X,[HT],[HNT]):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,[XT],[XComb]):N>0,N1 is N1,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([XT],[XComb]):comb2(T,Comb). comb2([_T],[XComb]):comb2(T,[XComb]).
This type of combination can contain an element more times. Thus, it is not a set but a multiset.
comb_rep(0,_,[]). comb_rep(N,[XT],[XRComb]):N>0,N1 is N1,comb_rep(N1,[XT],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,[HVaria]):N>0,N1 is N1,delete(H,L,Rest),varia(N1,Rest,Varia).
Again, this type of variation can contain repeated elements.
varia_rep(0,_,[]). varia_rep(N,L,[HRVaria]):N>0,N1 is N1,delete(H,L,_),varia_rep(N1,L,RVaria).


Designed and maintained by Roman Barták 