## Learning Prolog via Examples - 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).`

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

Last update 4^{th}
November 1997

Designed and maintained by Roman Bartak

© November 1997