все подмножества со всеми элементами списка в прологе

Question

Я пытаюсь вычислить список всех подмножеств данного списка со всеми его элементами, но до сих пор мне удалось найти подмножества из двух элементов, но это не является правильным решением для моей проблемы. Может ли кто-нибудь мне помочь? Я знаю, что такие проблемы, как это решается с помощью метода возвратов, но в Прологе, я не знаю, как это должно быть написано .. Исходный код выглядит так:

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). 

Заранее спасибо! :)

Answer 1

Используйте 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). 

Примеры запросов:

 
?- 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], []]. 

---

Итак ... как же list_allsubseqs/2 тариф по сравнению с findall/3 плюс list_subseq/2? Как насчет потребления памяти? Как насчет времени выполнения? Давайте копаем глубже!

Во-первых, для полноты картины, вот код хорошего-ола»ваниль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 , false). % hide some substitutions 
:- set_prolog_stack (global, limit(2*10**9)).  % cf. SWI-FAQ on "stack sizes" 

Давайте расследовать!

 
?- between (18, 22, N), 
    numlist (1, N, _Es), 
    member (How, [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 (globalused, 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.