在列表中找到一個缺失的號碼

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]. 

似乎工作。