问题 不经过一次删除不正确的后续解


我有一个谓词,找到正确的解决方案,但接着找到不正确的解决方案。

?- data(D),data_threshold_nonredundantbumps(D,5,Bs),write(D).
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([11], [7]), bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8], [6]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([9], [9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([11], [7]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([2, 3, 4], [6, 7, 8])] ;

等等

我们的想法是,它将在数据中找到所有非冗余的凸起,其中凸起是连续的子列表 data 就在上面 threshold,返回有序(按大小)列表 bump/2s 其中第一个arg of bump / 2是一个来自数据的指标列表,第二个arg是值列表。所以 bump([2, 3, 4], [6, 7, 8]) 意味着在数据指数2,3和4高于5时,它们是6,7,8。

如何添加条件以便找不到这些额外的解决方案? - 没有使用 once/1

如果我的代码可以通过其他方式简化,请告诉我。这似乎有点复杂,它正在尝试做什么。

所以:

这是我的代码:

:-use_module(library(clpfd)).

fd_length(L, N) :-
 N #>= 0,
 fd_length(L, N, 0).

fd_length([], N, N0) :-
 N #= N0.
fd_length([_|L], N, N0) :-
 N1 is N0+1,
 N #>= N1,
 fd_length(L, N, N1).

equidistant_stride([],_).
equidistant_stride([Z|Zs],D) :-
 foldl(equidistant_stride_(D),Zs,Z,_).

equidistant_stride_(D,Z1,Z0,Z1) :-
 Z1 #= Z0+D.

consecutive_ascending_integers(Zs) :-
 equidistant_stride(Zs,1).

consecutive_ascending_integers_from(Zs,Z0) :-
 Zs = [Z0|_],
 consecutive_ascending_integers(Zs).

bool01_t(1,true).
bool01_t(0,false).

if_(C_1,Then_0,Else_0) -->
 { call(C_1,Truth) },
 { functor(Truth,_,0) },  % safety check
 (  { Truth == true }  -> phrase(Then_0)
 ;  { Truth == false },   phrase(Else_0)
 ).

if_(If_1, Then_0, Else_0) :-
 call(If_1, T),
 (  T == true -> call(Then_0)
 ;  T == false -> call(Else_0)
 ;  nonvar(T) -> throw(error(type_error(boolean,T),_))
 ;  /* var(T) */ throw(error(instantiation_error,_))
 ).


 #=<(X,Y,Truth) :- X #=< Y #<==> B, bool01_t(B,Truth).

 #<( X,Y,Truth) :- X #<  Y #<==> B, bool01_t(B,Truth).

 #>( X,Y,Truth) :- X #>  Y #<==> B, bool01_t(B,Truth).

 #>=(X,Y,Truth) :- X #>= Y #<==> B, bool01_t(B,Truth).

tinclude(P_2,Xs,Zs) :-
 list_tinclude_list(Xs,P_2,Zs).

list_tinclude_list([],   _P_2,[]).
list_tinclude_list([i_v(E0,E1)|Es],P_2,Fs0) :-
 if_(call(P_2,E1), Fs0 = [i_v(E0,E1)|Fs], Fs0 = Fs),
 list_tinclude_list(Es,P_2,Fs).


tfilter(P_2,As,Bs) :-
 tinclude(P_2,As,Bs).

%% =====================================================================
%% =====================================================================

data([5,6,7,8,3,2,6,7]).

list_index_element(L,I,E):-
 nth1(I,L,E).  

filter(Threshold,DataPairs,FilterdPairs):-
 tfilter(#<(Threshold),DataPairs,FilterdPairs).

i_v_pair(I,V,i_v(I,V)).

data_indices_indicespairs(D,Is,Pairs):-
 same_length(D,Is),
 consecutive_ascending_integers_from(Is,1),
 maplist(i_v_pair,Is,D,Pairs).

list_ascending(List,MinLength,MaxLength):-
 Max in MinLength..MaxLength,
 labeling([max(Max)],[Max]),
 fd_length(List,Max),
 consecutive_ascending_integers(List).

region_minlength_maxlength(Region,MinLength,MaxLength,All):-
 list_ascending(Region,MinLength,MaxLength),
 append(_Before,End,All),
 append(Region,_End2,End).

data_threshold_bumpvalues_bumplocation(Data,Threshold,Bumpvalues,Bumplocation):-
 length(Data,MaxBump),
 data_indices_indicespairs(Data,_Is,Pairs),
 filter(Threshold,Pairs,FilteredPairs),
 maplist(i_v_pair,FilteredIndices,_FilteredValues,FilteredPairs),
 %Test =test(FilteredIndexes,FilteredValues),
 dif(Bumplocation,[]),
 region_minlength_maxlength(Bumplocation,0,MaxBump,FilteredIndices),
 maplist(list_index_element(Data), Bumplocation,Bumpvalues).


list_first_last([H|T],H,L):-
 last(T,L).

listoflists_firsts_lasts(Listoflists,Firsts,Lasts):-
 maplist(list_first_last,Listoflists,Firsts,Lasts).

%start is not between location1 and location2
start_location1_location2(Start,Location1,Location2) :-
 #\(   Location1 #=< Start,
 Start #=< Location2).

bumplocation_notsublist_of_any_acs(Bumplocation,Acs):-
 listoflists_firsts_lasts(Acs,Firsts,Lasts),
 %the start of bumplocation can not be between the start of any Acs
 Bumplocation =[Bumpstart|_],
 maplist(start_location1_location2(Bumpstart),Firsts,Lasts).


loc_val_bump(Location,Value,bump(Location,Value)).

data_bumplocations_bumpvalues(Data,Bumplocations,Bumpvalues):-
 maplist(list_index_element(Data),Bumplocations,Bumpvalues).

%this works but finds extra solutins so needs to be refined.
data_threshold_nonredundantbumps(Data,Threshold,Bumps):-
 data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumpslocations,[]),
 maplist(data_bumplocations_bumpvalues(Data),Nonredundantbumpslocations,Nonredundantbumps),
 maplist(loc_val_bump,Nonredundantbumpslocations,Nonredundantbumps,Bumps).

data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac0):-
 bumplocation_notsublist_of_any_acs(Bumplocation,Ac0),
 data_threshold_bumpvalues_bumplocation(Data,Threshold,_Bumpvalues,Bumplocation),
 append([Bumplocation],Ac0,Ac1),
 data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac1).

data_threshold_nonredundantbumps_ac(_Data,_Threshold,Ac0,Ac0).

8742
now


起源



答案:


我的印象是你稍微过度思考。有一个直截了当的表述 运行 超过阈值的数字,可以通过在列表的单个遍历中从头到尾考虑元素来定义。特别是,我们这样做  需要 append/3 去做这个。

一定要考虑使用 DCG表示法 ()在描述时 名单 在Prolog。在这种情况下,需要花一点时间来决定如何最好地应用DCG,因为我们正在描述  列表:

  • 的清单 运行 (连续元素超过阈值)
  • 在运行中,列表 指数 和

然而,除了一些技巧和扩展,DCG基本上只允许我们描述一个  列表,而不是同时单独的列表。因此,我们可以使用这种功能强大且可能非常合适的机制,并且必须选择我们要应用的列表 主要

在下文中,我展示了一个使用DCG来描述列表的解决方案 凸块/ 1 术语,也就是说,我“专用”机制来描述上面提到的第一种列表,并使用另一个DCG来描述 第二 一种列表,我通过它调用 phrase/2 来自第一个DCG。

data_threshold_bumps(Ds, T, Bs) :-
        phrase(bumps(Ds, 1, T), Bs).

bumps([], _, _) --> [].
bumps([D|Ds0], I0, T) -->
        { D #> T,
          phrase(bump(D, T, Ds0, Ds, I0, I), Bs) },
        [bump(Bs)],
        bumps(Ds, I, T).
bumps([D|Ds0], I0, T) -->
        { D #=< T,
          I #= I0 + 1 },
        bumps(Ds0, I, T).


bump(D, T, Ds0, Ds, I0, I) --> [I0-D],
        { I1 #= I0 + 1 },
        run(Ds0, Ds, T, I1, I).

run([], [], _, I, I) --> [].
run([D|Ds0], Ds, T, I0, I) --> [I0-D],
        { D #> T,
          I1 #= I0 + 1 },
        run(Ds0, Ds, T, I1, I).
run([D|Ds0], [D|Ds0], T, I, I) -->
        { D #=< T }.

示例查询和答案:

? -  data_threshold_bumps([3,6,7,8,2,4,5,6,9,4,7,3],5,Bs)。
Bs = [bump([2-6,3-7,4-8]),bump([8-6,9-9]),bump([11-7])] ;
假。

请注意,事实并非如此 相当 您需要的完全相同的数据表示,但将它转换为那个是微不足道的。

以下是一些改进此解决方案的想法,从更容易到更难:



答案: