子集，组合，排列的 prolog 解法

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

just_delete(X,[X|T],T).
just_delete(X,[H|T],[H|NT]) :- just_delete(X,T,NT).

combination(0,_,[]).
combination(K, L, [X|Xs]) :-
	K > 0,
	strip_delete(X,L,R),  
   	K1 is K-1,             % we already have choose one. still neeed K-1
   	combination(K1,R,Xs).  % then choose K-1 from R to Xs

subset([], []).
subset([E|L], [E|S]) :- subset(L, S).
subset(L, [_|S]) :- subset(L, S).

perm([],[]).
perm(List,[H|Perm]) :-  perm(Rest,Perm), just_delete(H,List,Rest).

求出全部结果

gen_sub(Set, Powerset) :- setof(Subset, subset(Subset, Set), Powerset).
gen_com(Set, N, Powerset) :- setof(Subset, combination(N, Set, Subset), Powerset).
gen_pem(Set, Powerset) :- setof(Subset, perm(Subset, Set), Powerset).

gen_pem([1,2,3], L) 可以求出结果。

<The Reasoned Schemer> 告诉我们

The First Commandment

Within each sequence of goals, move non-recursive goals before recursive goals.

交换一下顺序

perm1([],[]).
perm1(List,[H|Perm]) :- just_delete(H,List,Rest), perm1(Rest,Perm).
gen_pem1(Set, Powerset) :- setof(Subset, perm1(Set, Subset), Powerset).

探究一下 perm1 这里需要交换 Set 和 Subset 的原因。其中 我们按空格不断求解 :

perm(L, [1,2,3]) 可以成功。

perm([1,2,3], L) 求解出完全排列之后，不能停止。

perm1([1,2,3], L). 可以成功。

perm1(L, [1,2,3]).  只求解一个结果之后，不能停止

所以说什么导致了 prolog 不断的继续搜索。

规避这种搜索的有效方法，就是加上长度约束。

same_len([], []).
same_len([_|T1], [_|T2]) :-
    same_len(T1, T2).

perm([],[]).
perm(List,[H|Perm]) :-  same_len(List, [H|Perm]),perm(Rest,Perm), just_delete(H,List,Rest).