我正在尝试计算给定列表的所有子集及其所有元素的列表，但到目前为止我只成功找到了两个元素的子集，但这不是我的问题的正确解决方案..谁能帮忙我？我知道这样的问题是通过使用回溯方法解决的，但是在Prolog中，我不确定应该如何编写..源代码是这样的:
subs(_, [], []).
subs(H, [H1|Tail], [[H,H1]|Ta]):-
subs(H, Tail, Ta).
generatesubs([], []).
generatesubs([H], [H]).
generatesubs([H|Tail], [R|Ta]):-
subs(H, Tail, R),
generatesubs(Tail, Ta).
main1([], []).
main1([H], [H]):-
is_list(H).
main1([H|Tail], [H|Ta]):-
is_list(H),
main1(Tail, Ta).
main1([_|Tail], Ta):-
main1(Tail, Ta).
main([], []).
main(H ,R):-
generatesubs(H, G),
main1(G,R).
提前致谢! :)
最佳答案
使用 dcg !
list_allsubseqs(Es, Uss) :- list_acc_allsubseqs(Es, [[]], Uss). lists_prependum([] , _) --> []. lists_prependum([Es|Ess], E) --> [[E|Es]], lists_prependum(Ess, E). list_acc_allsubseqs([] , Uss , Uss). list_acc_allsubseqs([E|Es], Uss0, Uss) :- list_acc_allsubseqs(Es, Uss0, Uss1), phrase(lists_prependum(Uss1,E), Uss, Uss1).
Sample queries:
?- list_allsubseqs([], Xss).
Xss = [[]].
?- list_allsubseqs([a], Xss).
Xss = [[a], []].
?- list_allsubseqs([a,b], Xss).
Xss = [[a,b], [a], [b], []].
?- list_allsubseqs([a,b,c], Xss).
Xss = [[a,b,c], [a,b], [a,c], [a],
[b,c], [b], [c], []].
?- list_allsubseqs([a,b,c,d], Xss).
Xss = [[a,b,c,d], [a,b,c], [a,b,d], [a,b], [a,c,d], [a,c], [a,d], [a],
[b,c,d], [b,c], [b,d], [b], [c,d], [c], [d], []].
So... how does list_allsubseqs/2 fare in comparison to findall/3 plus list_subseq/2? What about memory consumption? What about runtime?Let's dig deeper!
First, for the sake of completeness, here's the code of good-ol' vanilla list_subseq/2:
list_subseq([], []).
list_subseq([E|Es], [E|Xs]) :- list_subseq(Es, Xs).
list_subseq([_|Es], Xs ) :- list_subseq(Es, Xs).
下面我们使用 swi-prolog 版本 7.3.11(64 位)。
:- set_prolog_flag ( toplevel_print_anon , 假)。 % 隐藏一些替换
:- set_prolog_stack (全局，限制(2*10**9))。 % 参照SWI-FAQ on "stack sizes"
让我们调查一下!
?- between (18, 22, N),
numlist (1, N, _Es),
member(如何，[findall_subseq，list_allsubseqs])，
garbage_collect ,
call_time (( How = findall_subseq, findall (Xs,list_subseq(_Es,Xs),_)
; How = list_allsubseqs, list_allsubseqs(_Es,_)), T_in_ms ),
statistics(全局使用，Mem_in_B)。
N = 18, How = findall_subseq, Mem_in_B = 62_915_848, T_in_ms = 185
; N = 18, How = list_allsubseqs, Mem_in_B = 12_584_904, T_in_ms = 22
;
N = 19, How = findall_subseq, Mem_in_B = 132_121_888, T_in_ms = 361
; N = 19，How = list_allsubseqs，Mem_in_B = 25_167_888，T_in_ms = 42
;
N = 20, How = findall_subseq, Mem_in_B = 276_825_400, T_in_ms = 804
; N = 20，How = list_allsubseqs，Mem_in_B = 50_333_784，T_in_ms = 80
;
N = 21, How = findall_subseq, Mem_in_B = 578_815_312, T_in_ms = 1_973
; N = 21, How = list_allsubseqs, Mem_in_B = 100_665_504, T_in_ms = 154
;
N = 22, How = findall_subseq, Mem_in_B = 1_207_960_936, T_in_ms = 3_966
; N = 22，How = list_allsubseqs，Mem_in_B = 201_328_872，T_in_ms = 290。
关于list - 序言中列表的所有元素的所有子集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33903135/