2

我正在尝试计算给定列表的所有子集及其所有元素的列表，但到目前为止，我只成功找到了两个元素的子集，但这不是我的问题的正确解决方案..任何人都可以帮忙我？我知道这样的问题是通过使用回溯的方法来解决的，但是在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).

提前致谢！:)

4

1 回答 1

3

使用！

list_allsubseqs（Es，Uss）：-
   list_acc_allsubseqs(Es, [[]], Uss)。

list_prependum([] , _) --> []。
list_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], [ a,d], [a],
         [b,c,d], [b,c], [b,d], [b], [c,d], [c], [d], []]。

那么...与pluslist_allsubseqs/2相比，票价如何？内存消耗呢？运行时呢？ 让我们深入挖掘！findall/3list_subseq/2

首先，为了完整起见，这里是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).

下面我们使用版本 7.3.11（64 位）。

:- set_prolog_flag ( toplevel_print_anon , false)。% 隐藏一些替换
:- set_prolog_stack (global, limit(2*10**9))。% 参照 关于“堆栈大小”的 SWI-FAQ

让我们调查一下！

?- 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 ),
   统计信息(globalused, Mem_in_B )。

  N = 18，如何 = findall_subseq，Mem_in_B = 62_915_848，T_in_ms = 185
; N = 18，如何 = list_allsubseqs，Mem_in_B = 12_584_904，T_in_ms = 22
;
  N = 19，如何 = findall_subseq，Mem_in_B = 132_121_888，T_in_ms = 361
; N = 19，如何 = list_allsubseqs，Mem_in_B = 25_167_888，T_in_ms = 42
;
  N = 20，如何 = findall_subseq，Mem_in_B = 276_825_400，T_in_ms = 804
; N = 20，如何 = list_allsubseqs，Mem_in_B = 50_333_784，T_in_ms = 80
;
  N = 21，如何 = findall_subseq，Mem_in_B = 578_815_312，T_in_ms = 1_973
; N = 21，如何 = list_allsubseqs，Mem_in_B = 100_665_504，T_in_ms = 154
;
  N = 22，如何 = findall_subseq，Mem_in_B = 1_207_960_936，T_in_ms = 3_966
; N = 22，如何 = list_allsubseqs，Mem_in_B = 201_328_872，T_in_ms = 290。
于 2015-11-26T22:44:34.790 回答