2

特定のリストのすべてのサブセットとそのすべての要素のリストを計算しようとしていますが、これまでのところ、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).

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], [ 、d]、[a]、
         [b,c,d]、[b,c]、[b,d]、[b]、[c,d]、[c]、[d]、[]]。

それで...プラスlist_allsubseqs/2と比較して運賃はどうですか？メモリ消費はどうですか？ランタイムはどうですか？ もっと深く掘り下げましょう！findall/3list_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).

以下では、バージョン 7.3.11 (64 ビット) を使用します。

:- set_prolog_flag ( toplevel_print_anon、false)。% 一部の置換を非表示
:- set_prolog_stack (グローバル、制限 (2*10**9))。% cf. 「スタック サイズ」に関する 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、How = list_allsubseqs、Mem_in_B = 201_328_872、T_in_ms = 290。
于 2015-11-26T22:44:34.790 に答える