正確的子集 - Prolog

Question

我正在嘗試編寫一個程序，它將兩個列表作爲輸入並檢查正確的子集。我開始：

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2]) :- proper(T1,T2). 

這適用於在以相同的順序輸入完全正常。例如：

?- proper([a,b,c],[a,b,c,d]). 
Yes 

，但不用於輸入，如：

?- proper([a,b,c],[b,d,a,c]). 
No 

通過網站尋找後，我發現這個以前問一個問題：

Subset function in prolog

導致我修改我的代碼，如下所示：

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

這適用於子集，但不適用於正確的子集。我認爲我的問題是由於我理解適當/ 4的第二項如何工作而引起的。任何和所有的幫助，不勝感激。

編輯：

意識到，我試圖以確定第一列表是第二和第二的真子集是第一的真子集。清理代碼更加精確。

proper([],_). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

Answer 1

如果我理解正確的話，在你的最後一次嘗試前兩個聲明將意味着，都 1個元素的列表是空列表（假）的一個子集，和一個空列表是包含一個元素的列表的真正子集（true）;第一個應該是有問題的，因爲proper([1], [])會成功以及proper([],[1])，但是正確的子集關係是不對稱的。

我相信，你的第二次嘗試不篩選出相同的子集的原因是你沒有申報，需要一個比B.

較小這裏是我想出了一些可能的解決方案。我多次使用smaller_set/2以提高清晰度和簡潔性。

smaller_set(A, B) :- 
    length(A, LA), 
    length(B, LB), 
    LA < LB. 

def_proper_subset/2試圖捕獲子集的標準定義。

def_proper_subset(A, B) :- 
    smaller_set(A, B),     % if A < B then there's some _e in B that isn't in A. 
    forall(member(_e, A), member(_e, B)). 

與遞歸定義，基於removeing它確保A的各匹配元件和B.一個例子是A <乙僅通過隨後的如果A用完元件B.

之前

rec_proper_subset1([], [_|_]). 
rec_proper_subset1([_e|A], B) :- 
    select(_e, B, C),   % C is B with _e removed. Only true if _e is in B. 
    rec_proper_subset1(A, C). 

這一旦主謂詞已經確定A使用輔助謂詞來檢查成員資格A < B.

rec_proper_subset2(A, B) :- 
    smaller_set(A, B), 
    rec_proper_subset2_(A, B). 

rec_proper_subset2_([], _). 
rec_proper_subset2_([_e|A], B) :- 
    member(_e, B), 
    rec_proper_subset2_(A, B). 

編輯：

• 你需要，如果你想確保你的名單沒有任何重複的元素使用list_to_set/2，sort/2，或者類似的東西。但是這些解決方案也將用於查找子列表。
• 我認爲def_proper_subset/2是一種蹩腳的解決方案，因爲它只會檢查A是B的子集，但不能在A中生成B的子集。其他兩個都能夠想到。

（我搞砸了，忘了包括地面定義rec_proper_subset2/2，但現在我有固定的）。