CODEWITHSUNDEEP
listprologinteger
Hunterhod
Hunterhod

Reputation: 185

Finding missing integers - Prolog

I want to take a list of integers and create a list of the integers which are between (or in the gaps of) the integers in the former list. For example, I'd like ?- findmissing([1,3,4,5,6],X). to result in X = [2]. How would I implement such a function?

Upvotes: 0

Views: 660

Answers (2)

hardmath
hardmath

Reputation: 8823

Conrad Irwin has here given a nice analysis of solving the problem recursively but assumes the input list is sorted in ascending order (as was the case in the example Hunterhod posed).

Thinking about the possibility of unsorted input suggests an approach besides just sorting the input before applying Conrad's technique.

  1. Find the Minimum and Maximum elements of InputList.

  2. Create the list of consecutive integers BetweenList = [Minimum,...,Maximum].

  3. Extract from BetweenList all entries not members of InputList to form MissingList.

Upvotes: 1

Conrad Irwin
Conrad Irwin

Reputation: 1312

The first trick with logic programming is to start with the smallest cases and work up.

The base cases here are easy, if there are fewer than two elements in the list, there's nothing missing.

findmissing([], []).
findmissing([_], []).

The second trick is to divide and conquer. To find everything missing between each pair in the List, we'll need a predicate (say numbersbetween(X, Y, List)/3) that gives all of the numbers between a given pair of numbers, and then to run that on each pair in the input List. Using the builtin append()/3, and not worrying for the moment about how to implement numbersbetween()/3, we can just put:

 findmissing([X, Y|In], Out) :-
     numbersbetween(X, Y, Between),
     findmissing([Y|In], After),
     append(Between, After, Out).

(There's a bit of care taken here to make sure we consider every pair, in the list [1,2,3], we need to check [1,2] and [2,3] — that's why the recusive step takes [Y|In] not just In).

That then only leaves the challenge of defining numbersbetween()/3. If you happen to know about the inbuilt predicates between()/3, (that is true if X < Z < Y), and setof()/3 (which can generate a List from all solutions), you can go with:

numbersbetween(X, Y, List) :- setof(B, between(X, Y, B), List).

If you don't happen to know about those functions, you can construct your own numbersbetween(), using Prolog's arithmetic "is".

Upvotes: 3

Related Questions