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

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),
   фраза(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], [ а, д], [а],
         [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). % скрыть некоторые замены: - set_prolog_stack(global, limit (2 * 10 ** 9)). % ср. SWI-FAQ по "размерам стека"

Давайте исследуем!

? - между(18, 22, N), numlist(1, N, _Es), член(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), статистика(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.