### Guide to Prolog Programming © Roman Barták, 1998 Home Prolog in Examples Prolog Data Structures List Processing Previous | Contents | Next Combinatorics

[permutations] [combinations] [variations]

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.

 Designed and maintained by Roman Barták