在列表中找到一个缺失的号码

Question

假设我有一个列表[2,1,4,5]，我想要一个谓词返回3作为缺少的元素。

missing([], []). 
missing([H|T], R) :- missing([H|T], H, R). 
missing([], _I, []). 
missing([H|T], I, [I|R]) :- 
    H =\= I, 
    !, 
    NextI is I + 1, 
    missing([H|T], NextI, R). 
missing([_|T], I, R) :- 
    NextI is I + 1, 
    missing(T, NextI, R). 

但它不适用于未排序的列表。

Answer 1

如果您的实现在未排序列表上不起作用，最简单的解决方法是在执行算法之前对输入列表进行排序。您可以通过将sort/2谓词添加到当前的实现中来完成此操作。

missing([], []). 
missing(Raw, R):- 
    sort(Raw, [H|T]), 
    missing([H|T], H, R). 
missing([], _I, []). 
missing([H|T], I, [I|R]):- 
    H =\= I, 
    !, 
    NextI is I + 1, 
    missing([H|T], NextI, R). 
missing([_|T], I, R):- 
    NextI is I + 1, 
    missing(T, NextI, R). 

测试：

?- missing([1,2,6], M). 
M = [3, 4, 5]. 

?- missing([1,2,6,-1], M). 
M = [0, 3, 4, 5]. 

?- missing([-1, 5], M). 
M = [0, 1, 2, 3, 4]. 

?- missing([-1, 5, -3], M). 
M = [-2, 0, 1, 2, 3, 4]. 

?- missing([5, -3], M). 
M = [-2, -1, 0, 1, 2, 3, 4]. 

似乎工作。