序言no_duplicate函數

我想寫一個簡單的過程，檢查列表是否有任何重複。這是我迄今爲止所嘗試的：序言no_duplicate函數

% returns true if the list has no duplicate items. 
no_duplicates([X|XS]) :- member(X,XS) -> false ; no_duplicates(XS). 
no_duplicates([]) :- true.

如果我嘗試no_duplicates([1,2,3,3])。它說的是真的。爲什麼是這樣？我可能在這裏誤解了Prolog，但任何幫助表示讚賞。

來源

2014-09-25 Nathan

我假設你正在使用SWI Prolog的（因爲你有問題的SWI-Prolog的標籤）。我用SWI 6.6.6測試了你的程序，它適用於你提到的情況，給了我'錯誤'。 – Jay 2014-09-25 20:25:19

這很奇怪..我也使用6.6.6，它給了我真實的。 – Nathan 2014-09-25 20:39:00

你是如何加載代碼的？你有沒有把它放在一個文件中（比如說''dup.prolog'「），然後用'['dup.prolog']將它加載到SWI中''在詢問查詢之前？ – Jay 2014-09-25 22:44:57

我想在這個問題去更多描述性：

no_duplicates([] ) . % the empty list is unique 
no_duplicates([X|Xs]) :- % a list of length 1+ is unique 
    \+ member(X,Xs) ,  % - if its head is not found in the tail, 
    no_duplicates(Xs)  % - and its tail is itself unique. 
    .      %

考慮到這一點，因爲這是一個有點昂貴的操作— O（n ）？ —使用sort/2可能會更高效，並利用它生成有序集的事實，刪除重複項。你可以這樣說：

no_duplicates(L) :- 
    sort(L,R)  % sort the source list, removing duplicates 
    length(L,N) , % determine the length of the source list 
    Length(R,N) , % check that against the result list 
    .

或者你可以使用msort/3（不刪除重複的），可能會更快一點，也：

no_duplicates(L) :- 
    msort(L,R),   % order the list 
    \+ append(_,[X,X|_],R) % see if we can find two consecutive identical members 
    .

來源

2014-09-25 21:44:58

OP的解決方案是正確的。而你們給出了一個選擇，所以它不是錯誤的，但是在列表中沒有兩種不重複的方式。所以這不是一個好的解決方案。我會刪除singelton列表案例。 – 2014-09-26 12:47:47

最後一個版本使用'msort/2'和語法統一，比原來的解決方案暴露出更加不穩定的行爲。 – false 2014-09-26 20:52:39

重複列表中的相同元素並不在列表中的同一個地方，所以no_duplicates可以寫成：

no_duplicates(L) :- 
    \+((nth0(Id1, L, V), nth0(Id2, L, V), Id1 \= Id2)).

來源

2014-09-25 21:04:33 joel76

你也可以嘗試'append（_，[E | R]，L），成員（E，R）' - 可能會更快，因爲它避免了明確的比較。 – liori 2014-09-25 22:48:53

@liori：這減少了n²的統一。 – false 2014-09-26 10:46:38

周杰倫已經注意到，您的代碼工作。另一種，略少冗長

no_duplicates(L) :- \+ (append(_, [X|XS], L), memberchk(X, XS)).

來源

2014-09-25 22:02:24 CapelliC

這裏的另一種方法，它的作品，因爲sort/2刪除重複：

no_duplicates(L) :- 
    length(L, N), 
    sort(L, LS), 
    length(LS, N).

來源

2014-09-26 02:13:22 lurker

回答您的問題：如預期no_duplicates([1,2,3,3])您的解決方案實際上是失敗。所以沒有問題。

現在採取的查詢：

?- A = 1, no_duplicates([A, 2]). 
A = 1. 
?-  no_duplicates([A, 2]), A = 1.

他們都意味着同樣的，所以我們應該預料到的Prolog會產生相同的答案。（_{更準確地說，我們期望相同的忽略錯誤和不終止}）。

然而，四種提出的解決方案不同！而不是，差異爲：

?- A = 2, no_duplicates([A, 2]). 
false. 
?-  no_duplicates([A, 2]), A = 2.

請注意，它總是第二個查詢，使麻煩。要解決這個問題，我們需要一個很好的答案no_duplicates([A, 2])。它不能是false，因爲A有一些值可以使其成立。像A = 1。它也不是真的，因爲有些值不適合，比如A = 2。

另一種可能性是在這種情況下發出instantiation_error。含義：我沒有足夠的信息，所以我最好停下來解決可能不正確的信息。

理想情況下，我們得到一個涵蓋所有可能解決方案的答案。這個答案是dif(A, 2)，這意味着所有不同於2的A都是解決方案。

dif/2是最古老的內置謂詞之一，已經Prolog 0擁有它。不幸的是，後來的開發在Prolog I中丟棄了它，因此在愛丁堡Prolog和ISO Prolog中丟棄了它。

但是，目前的系統包括SICStus，YAP，SWI都提供它。並有一個安全的方式來approximate dif/2 safely在ISO-Prolog的

no_duplicates(Xs) :- 
    all_different(Xs). % the common name 

all_different([]). 
all_different([X|Xs]) :- 
    maplist(dif(X),Xs). 
    all_different(Xs).

參見：prolog-dif

來源

2014-09-26 10:33:47 false

序言no_duplicate函數

回答

相關問題