Prolog：使我的谓词return所有可能的解决方案

Question

我在prolog online的99-problems中发现了这个问题。有一个解决方案（与我的无关），我想知道为什么我的不起作用。或者更确切地说：它有效，但它只找到 1 个解决方案而不是所有解决方案。问题是这样表述的： a) 一个 9 人的小组在 2、3 和 4 人的 3 个不相交的子小组中有多少种工作方式？

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

append(X,[],X).
append([],X,X).
append([H|R], [A|B], [H|W]):- append(R,[A|B],W).

group234(G,G2,G3,G4):- length(G2,2),
                       length(G3,3),
                       length(G4,4),
                       member(X,G),
                       member(Y,G),
                       member(Z,G),
                       member(X,G2),
                       member(Y,G2),
                       member(Z,G3),
                       append(G2,G3,I),append(I,G4,G).

q1: 有没有办法像我一样使用 length 和 append 和 member 并成功地解决这个问题，还是我需要完全重写这个？
q2：为什么这段代码只产生 1 个解？ Prolog 应该搜索许多可能的成员，不是吗？（显然，它不应该，因为该语言比我更了解。但据我了解它应该，为什么不呢？）

Answer 1

你只需要append/3定义一个谓词来选择和删除一组中的一个人：

choose(X, L1, L2) :-
    append(A, [X|B], L1),
    append(A, B, L2).

例如：

?- choose(X, [a,b,c], Rest).
X = a,
Rest = [b, c] ;
X = b,
Rest = [a, c] ;
X = c,
Rest = [a, b] ;
false.

然后，使用这个谓词，您可以将 group234/4 定义为：

group234(G, [A,B], [C,D,E], G4):-
    choose(A, G,  G0),
    choose(B, G0, G1), A @< B,
    choose(C, G1, G2), 
    choose(D, G2, G3), C @< D,
    choose(E, G3, G4), D @< E.

请注意，您需要条件 A @< B，以 避免排列 （因为两个列表 [A,B] 和 [B,A] 代表同一组）。类似地，条件 C @< D 和 D @< E 避免列表 [C,D,E].

的排列

示例：

?- group234([a,b,c,d,e,f,g,h,i], G2, G3, G4).
G2 = [a, b],
G3 = [c, d, e],
G4 = [f, g, h, i] ;
G2 = [a, b],
G3 = [c, d, f],
G4 = [e, g, h, i] ;
G2 = [a, b],
G3 = [c, d, g],
G4 = [e, f, h, i] ;
G2 = [a, b],
G3 = [c, d, h],
G4 = [e, f, g, i] 
...

Answer 2

我认为问题的表述相当含糊。 @slago 提出的（很好！+1）解决方案依赖于可排序的元素，但我认为解决方案应该在列表的 positions 上进行表达。这是他们完成的解决方案，使用库谓词表示：

%!  %%%%

group234(G, [A,B], [C,D,E], G4):-
    select(A, G,  G0),
    select(B, G0, G1), A @< B,
    select(C, G1, G2),
    select(D, G2, G3), C @< D,
    select(E, G3, G4), D @< E.

n_group234_slago(N) :-
    numlist(1,9,L),
    aggregate_all(count,group234(L,_,_,_),N).

这是我的

take_ordered(L,[X],R) :-
    select(X,L,R).
take_ordered(L,[X|Xs],R) :-
    append(H,[X|T],L),
    take_ordered(T,Xs,J),
    append(H,J,R).

group234_cc(L,[A1,A2],[B1,B2,B3],[C1,C2,C3,C4]) :-
    take_ordered(L,[A1,A2],U),
    take_ordered(U,[B1,B2,B3],[C1,C2,C3,C4]).

n_group234_cc(N) :-
    numlist(1,9,L),
    aggregate_all(count,group234_cc(L,_A,_B,_C),N).

两者 n_group234_slago(N)、n_group234_cc(N) return 都请求了正确的数字 N。

编辑

我对take_ordered/3不满意。然后，我试着用一个DCG来表达：

take_ordered([],[]) --> [].
take_ordered([X|Xs],Ys) --> [X],
    take_ordered(Xs,Ys).
take_ordered(Xs,[Y|Ys]) --> [Y],
    take_ordered(Xs,Ys).

take_ordered(L,O,R) :-
    phrase(take_ordered(O,R),L).

效率显着提高，推理计数减半。

编辑

'P-99: Ninety-Nine Prolog Problems' 站点提出的解决方案 group3/4 比您在此处找到的@slago 和我的提议效率低得多。

?- numlist(1,9,L),time(aggregate_all(count,group3(L,A,B,C),N)).
% 122,373 inferences, ...

?- time(n_group234_cc(N)).
% 7,549 inferences, ...

Prolog：使我的谓词return所有可能的解决方案

Prolog :Make my predicate return all possible solutions

prolog