Prolog - Combination Operations

---

---

Combination

Combination refers to selection of elements from a set of element in any order. A combination is generally a subset. For example, in case of a List, [a, b, c], the possible combinations of two elements are as following −

 [a, b], [a, c], [b, c] 

Here [b, a] is treated same as [a, b] as order is not considered in combination operation.

Defining a Combination Predicate

We're defining a custom combination predicate with following syntax −

 combination(+K, +List, -CombinationResult) 

Where −

• K − Number of items to be selected.

• List − Source List of elements

• CombinationResult − Resulted Combination

To design this predicate, we can follow few observations as given below −

• If the list is empty, then combination list must also be empty.

• We can exclude header from the combination and take List of form [_|Tail].

• Now call the combination recursively with K, Tail and CombinationResult.

Program (list_repos.pl)

 combination(0, _, []). combination(K, [Head|Tail], [Head|C]) :- K > 0, K1 is K - 1, combination(K1, Tail, C). combination(K, [_|Tail], C) :- K > 0, combination(K, Tail, C). 

Output

 | ?- consult('D:/TP Prolog/Sample Codes/list_repos.pl'). compiling D:/TP Prolog/Sample Codes/list_repos.pl for byte code... D:/TP Prolog/Sample Codes/list_repos.pl compiled, 2 lines read - 1252 bytes written, 4 ms yes | ?- combination(2, [a, b, c], C). C = [a,b] ? a C = [a,c] C = [b,c] no 

Selecting 0 Element Combination

 | ?- combination(0, [a, b, c], C). C = [] ? a no 

Using more elements to select than List Size.

 | ?- combination(4, [a, b, c], C). no | ?- 

Explanation

• combination(0, _, []) is the base case of recursive call as selecting 0 element from a list is to result in empty list.

• combination(K, [Head|Tail], [Head|C]) :- K > 0, K1 is K - 1, combination(K1, Tail, C) is recursive call where X is head element of the list and is included in each combination.

• combination(K, [_|Tail], C) :- K > 0, combination(K, Tail, C) is recursive call where head element of the list is excluded from each combination.