的Prolog - 除去非獨特元素

我有一個謂詞來檢查元件是列表的成員，並期待如下：的Prolog - 除去非獨特元素

member(X,[X|_]). 
member(X,[_|T]) :- member(X,T).

當我打電話： - 部件（1，[2,3， 1,4]）我得到：true。

而現在我必須用它來寫謂詞將從列表中的列表中刪除所有非唯一元素，如下列：

remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]],X). 
X = [[t],[w],[i,b,b],[z,c]]

我怎麼能這樣做？

來源

2017-06-05 user

爲什麼'X = [[T]，[K，W]，[I，B，B]，[Z，C]] '？在[[a，m，t，a]，[k，a，w]，[i，k，b，b]，[z，m，m，c]]'和'b在解決方案中出現兩次。這沒有多大意義。 – lurker

抱歉，這是我的錯誤 – user

@lurker：'b，b'在這裏是因爲它只出現在一個子列表中 - 大概是 – false

以您的示例和@ false的評論爲例，實際問題似乎是從每個子列表中刪除發生在任何其他子列表中的元素。我的困難將其概念化爲單詞，導致我構建了我認爲是非常混亂和粗糙的一段代碼。

所以首先我想要一個小助手謂詞排序member/2直到列表子列表。

in_sublist(X, [Sublist|_]) :- member(X, Sublist). 
in_sublist(X, [_|Sublists]) :- in_sublist(X, Sublists).

這是沒有很大的一塊工作，並於實話我覺得，因爲我只是不能看到自己曾經想使用這個對自己應該以某種方式內聯。

現在，我最初的解決方案是不正確的，看起來像這樣：

remove([Sub1|Subs], [Res1|Result]) :- 
    findall(X, (member(X, Sub1), \+ in_sublist(X, Subs)), Res1), 
    remove(Subs, Result). 
remove([], []).

你可以看到那種主題的我要去這裏雖然：讓我們用findall/3枚舉子列表的元素在這裏然後我們可以過濾掉其他列表中出現的那些。這並不完美，輸出看起來像這樣。

?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R). 
R = [[t], [a, w], [i, k, b, b], [z, m, m, c]].

所以，它開始尋求與[t] OK，但隨後失去與[a,w]的情節，因爲沒有可視性輸入[a,m,t,a]當我們到達第一個遞歸調用。有幾種方法可以處理它;一個聰明的人可能會形成一種拉鍊，我們將列表中的前面的元素和後面的元素放在一起。另一種方法是在遞歸調用之前從所有後續列表中刪除列表中的元素。我選擇了一個「更簡單」的解決方案，該解決方案更加複雜，難以閱讀，但花費的時間更少。我強烈建議您調查其他可讀性選項。

remove(In, Out) :- remove(In, Out, []). 
remove([Sub1|Subs], [Res1|Result], Seen) :- 
    findall(X, (member(X, Sub1), 
       \+ member(X, Seen), 
       \+ in_sublist(X, Subs)), Res1), 
    append(Sub1, Seen, Seen1), 
    remove(Subs, Result, Seen1). 
remove([], [], _).

所以基本上現在我保持一個「看到」列表。在遞歸調用之前，我把目前爲止所看到的東西以及這個列表中的元素縫合在一起。這不是特別有效，但它似乎完成了這項工作：

?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R). 
R = [[t], [w], [i, b, b], [z, c]].

這讓我覺得很討厭的問題。老實說，我很驚訝這是多麼令人討厭。我希望別人能夠走到一起，找到更好的解決方案。

要調查的另一件事是DCGs，這可以幫助做這些類型的列表處理任務。

來源

2017-06-05 14:56:34

非常感謝，但這意味着\ +？ – user

謂詞findall過於先進。我只能使用我的謂詞。 – user

'\ +'表示否定。 –

使用library(reif)爲 SICStus | SWI：

lists_uniques(Xss, Yss) :- 
    maplist(tfilter(in_unique_t(Xss)), Xss, Yss). 

in_unique_t(Xss, E, T) :- 
    tfilter(memberd_t(E), Xss, [_|Rs]), 
    =(Rs, [], T).

注，雖然沒有限制如何命名謂語，非關係，必須經常名稱背後隱藏的純關係。 remove是一個真正的必要條件，但我們只想要一個關係。列表列表與僅具有唯一元素的列表列表之間的關係。

使用示例：

?- lists_uniques([[X,b],[b]], [[X],[]]). 
dif(X, b).

因此，在這種情況下，我們都留下X一個非實例變量。因此，Prolog計算可能的最一般的答案，找出X的樣子。

（請注意，已經接受不正確的回答在這種情況下失敗）

來源

2017-06-05 17:07:05 false

確實有更高效的版本：特別是，其他元素的數量太多了。 – false

謝謝，但我無法使用任何圖書館，因爲這是我大學的任務。 – user

將庫複製到您的解決方案中！ – false

的Prolog - 除去非獨特元素

回答

相關問題