prolog - 在列表中查找缺失的号码

Question

假设我有一个 List [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].

似乎工作。