Learning Prolog via Examples - Combinatorics


 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?


permutations

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).


combinations

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]).


combinations with repeated elements

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.


variations

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).


variations with repeated elements

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).


Combinatorics is powerfull to express complexity of algorithm but do not incorporate it in your programs.


 Part of INTERACTIVE PROLOG GUIDE  Prev TOC Next 


Last update 4th November 1997
Designed and maintained by Roman Bartak
© November 1997