Guide to Prolog Programming	© Roman Barták, 1998
Home Prolog in Examples Prolog Data Structures List Processing	Previous | Contents | Next
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?

---

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

Designed and maintained by Roman Barták	Previous | Contents | Next