PrologはList内のすべてのペアを述語化しますか？

Question

私はPrologスクリプトに一連の可能性を持っており、リストのすべてのペアに適用される特定の述語が真と評価する最大のセットを見つけたいと考えています。

簡略化した例は人の集合であり、すべてが相互の友人である最大のグループを探したいとします。だから、与えられた：

% Four-way friend CIRCLE 
link(tom, bill). 
link(bill, dick). 
link(dick, joe). 
link(joe, tom). 

% Four-way friend WEB 
link(jill, sally). 
link(sally, beth). 
link(beth, sue). 
link(sue, jill). 
link(jill, beth). 
link(sally, sue). 

% For this example, all friendships are mutual 
friend(P1, P2) :- link(P1, P2); link(P2, P1). 

可能な一致は、（明確にするため、アルファベット順に各ペアを提示）する必要があります。

% the two-person parts of both sets : 
[bill, tom], [bill, dick], [dick, joe], [joe, tom], 
[jill, sally], [beth, sally], [beth, sue], [jill, sue], 
    [beth, jill], [sally, sue] 

% any three of the web : 
[beth, jill, sally], [beth, sally, sue], [beth, jill, sue] 

% and the four-person web : 
[beth, jill, sally, sue] 

私はすべての二人はと一致見つけることができます：

% Mutual friends? 
friendCircle([Person1, Person2]) :- 
    friend(Person1, Person2), 
    % Only keep the alphabetical-order set: 
    sort([Person1, Person2], [Person1, Person2]). 

しかし、私は大きなセットを見つけようとしているのにうんざりする。

friendCircle([Person1|Tail]) :- 
    friendWithList(Person1, Tail), 
    Tail = [Person2|Tail2], 
    % Only keep if in alphabetical order: 
    sort([Person1, Person2], [Person1, Person2]), 
    friendWithList(Person2, Tail2). 

% Check all members of the list for mutual friendship with Person: 
friendWithList(Person, [Head|Tail]) :- 
    friend(Person, Head), % Check first person in list 
    friendWithList(Person, Tail). % Check rest of list 

しかし、私がそれを実行すると、2人の人物のリストを列挙した後、Prologがハングアップし、最終的にスタック領域がなくなります。私は間違って何をしていますか？

私は何をしようとしていることは五友人Web用友の状態のためにこれらの対の各々をチェックすることになるウェブを、歩くされています。私は私の2つのfriendsWithList/2通話考えたものである

(1,2) (1,3), (1,4), (1,5) % Compare element 1 with the rest of the list 
     (2,3), (2,4), (2,5) % Remove element 1 and repeat 
      (3,4), (3,5) 
        (4,5) 

friendCircle/1ルールでしていました。

Answer 1

私はあなたがループに入っていると思います。友人サークルを構築するときに友だちに「訪問した」かどうかを確認する必要があります。

friendCircle(Friends):- 
    findall(SFriendCircle, 
    (
     friend(Person1, Person2), 
     friendCircle([Person1, Person2], FriendCircle), 
     sort(FriendCircle, SFriendCircle) 
    ), 
    LFriends), 
    sort(LFriends, SFriends), 
    member(Friends, SFriends). 

friendCircle([From|Tail], Friends):- 
    friend(From, To), 
    \+ member(To, Tail), 
    forall(member(Friend, Tail), friend(To, Friend)), 
    friendCircle([To,From|Tail], Friends). 
friendCircle(Friends, Friends). 

テスト：この上

私のテイク

?- friendCircle(Friends). 
Friends = [ben, tom] ; 
Friends = [dick, joe] ; 
Friends = [dick, joe, tom] ; 
Friends = [dick, tom] ; 
Friends = [joe, tom]. 

Answer 2

はここで、bagofを排除する、私は（追加明確にするためのコメントで）使用して終了クリーンアップバージョンだsortとfindallコール（あなたのプロローグにそれがない場合はforall）：

% Four-way friend CIRCLE 
link(tom, bill). 
link(bill, dick). 
link(dick, joe). 
link(joe, tom). 

% Four-way friend WEB 
link(jill, sally). 
link(sally, beth). 
link(beth, sue). 
link(sue, jill). 
link(jill, beth). 
link(sally, sue). 

% Assume if one is friends with the other, it's reflexive 
friend(Person1, Person2) :- (link(Person1, Person2); link(Person2, Person1)). 

% Replace a forall/2 call 
friendWithList(_, []). 
friendWithList(Person, [Friend|Tail]) :- 
    friend(Person, Friend), 
    friendWithList(Person, Tail). 

% Build a friend web 
friendCircle(Friends):- 
    friend(Person1, Person2), % Start with two random friends... 
    Person1 @=< Person2, % ...who are in alphabetical order. 
    validCircle([Person1, Person2], Friends). % Build a web with them. 


% Given a valid web in the first parameter, 
% find a valid web and put it in the second parameter. 

% Because the input is a valid web, the simplest output is itself: 
validCircle(Friends, Friends). 

% The other option is to try and grow the web: 
validCircle([Person|Tail], Output):- 
    friend(Person, NewGuy), % Grab a friend of the first person in the list... 
    NewGuy @=< Person, % ...who alphabetically comes before that person... 
    \+ member(NewGuy, Tail), % ...and we don't have in the list already. 

    % Check that the new guy is friends with everyone already on the list 
    % If you have the forall/2 predicate, 
    % you can swap the comment on the next two lines 
    friendWithList(NewGuy, Tail), 
    %forall(member(ExistingFriend, Tail), friend(NewGuy, ExistingFriend)), 

    % Build a valid circle with the new inputs, 
    % and put that in the output slot. 
    validCircle([NewGuy,Person|Tail], Output). 

Answer 3

この観察

?- setof(Friend, friend(Person, Friend), Friends). 
Person = beth, 
Friends = [jill, sally, sue] ; 
Person = bill, 
Friends = [dick, tom] ; 
.... 

書くために私をリード：

pair(P1, A, B) :- 
    append(_, [A|As], P1), 
    append(_, [B|_], As). 

circles(Cs) :- 
    setof(C, X^P^A^B^(setof(Person, friend(Person, X), P), 
       forall(pair(P, A, B), friend(A, B)), 
       sort([X|P], C) 
      ), Cs). 

この結果と

?- circles(L). 
L = [[beth, jill, sally, sue]].