Удалить неправильные последующие решения без единого

Question

У меня есть предикат, который находит правильное решение, но затем продолжает искать решения, которые не верны.

?- 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 где первый аргумент bump/2 является списком признаков из данных, а второй аргумент является списком значений. Так 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).

Answer 1

У меня сложилось впечатление, что вы немного обдумываете это. Существует прямая формулировка для серий чисел, которые превышают пороговое значение, которое можно определить, рассматривая элементы от первого до последнего в одном обходе списка. В частности, нам не нужно append/3 сделать это.

Всегда рассматривайте возможность использования записи DCG ( dcg) при описании списков в Прологе. В этом случае требуется время, чтобы подумать, как лучше всего применять DCG, потому что мы описываем два списка:

• списки прогонов (последовательные элементы, превышающие порог)
• внутри прогонов, списки индексов и значений.

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

Далее я покажу решение, которое использует DCG для описания списка терминов bump/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 = [удар ([2-6, 3-7, 4-8]), удар ([8-6, 9-9]), удар ([11-7])];
ложный.

Обратите внимание, что это не совсем то же представление данных, которое вам нужно, но его просто преобразовать в это.

Вот несколько идей по улучшению этого решения, от простого к сложному:

• Избавьтесь от ненужных точек выбора, используя if_/3,
• Имеет ли смысл использовать нотацию DCG для bumps//3 а также run//5 в коде выше? Каковы преимущества и недостатки использования DCG здесь по сравнению с обычными предикатами?
• Поиграйте с разными взглядами на проблему. Можете ли вы изменить представление DCG? Например, как насчет описания фактических данных с помощью DCG вместо выпуклостей?
• Отследите источник нежелательных решений в коде, который вы разместили.

Кстати, чтобы снять ограничение (reifiable) CLP(FD), вам нужно использовать (#/\)/2 обозначить соединение. Не работает с (,)/2,

Answer 2

В следующем коде вы найдете несколько разделов, заключенных в скобки

:- if(false).
...
:- endif.

все эти разделы дают одинаковый результат

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

Сам код - это всего лишь приложение сопоставления с образцом, и, от последнего к первому, показан возможный способ рефакторинга того же базового предиката bump/5, чтобы улучшить читаемость (но, по правде говоря, мой предпочтительный - последний...)

data_threshold_bumps(Es, T, Sorted) :-
    bumps(Es, 1, T, Bs),
    predsort(by_len, Bs, Sorted).

bumps([], _, _, []).
bumps([E|Es], P, T, Bs) :-
    succ(P, Q),
    bumps(Es, Q, T, Cs),
    bump(E, P, T, Cs, Bs).

by_len(<, bump(Xs,_), bump(Ys,_)) :-
    length(Xs, Xl),
    length(Ys, Yl), Xl < Yl.
by_len(>, _, _).

:- use_module(library(clpfd)).

bump(E, _, T, Bs, Bs) :- E #=< T.
bump(E, P, T, Cs, Bs) :- E #> T, elem_placed(E, P, Cs, Bs).

elem_placed(E, P, [], [bump([P], [E])]).
elem_placed(E, P, [X|Bs], [Y|Bs]) :-
    X = bump([Q|Ps], [F|Es]),
    P #= Q-1,
    Y = bump([P,Q|Ps], [E,F|Es]).
elem_placed(E, P, [X|Bs], [bump([P],[E]), X|Bs]) :-
    X = bump([Q|_Ps], _Es),
    P #\= Q-1.

:- if(false).

bump(E, _, T, Bs, Bs) :- E =< T.
bump(E, P, T, Cs, Bs) :- E > T, elem_placed(E, P, Cs, Bs).

% first stored: tail
elem_placed(E, P, [], [bump([P], [E])]).
% extend current
elem_placed(E, P, [X|Bs], [Y|Bs]) :-
    X = bump([Q|Ps], [F|Es]),
    succ(P, Q),
    Y = bump([P,Q|Ps], [E,F|Es]).
% place new
elem_placed(E, P, [X|Bs], [bump([P],[E]), X|Bs]) :-
    X = bump([Q|_Ps], _Es),
    \+ succ(P, Q).

:- endif.

:- if(false).

bump(E, _, T, Bs, Bs) :- E =< T.
bump(E, P, T, Cs, Bs) :- E > T, enabled(E, P, Cs, Bs).

enabled(E, P, [], [bump([P], [E])]).
enabled(E, P, [bump([Q|Ps], [F|Es])|Bs], [bump([P,Q|Ps], [E,F|Es])|Bs]) :- succ(P, Q).
enabled(E, P, [bump([Q|Ps], [F|Es])|Bs], [bump([P],[E]), bump([Q|Ps],[F|Es])|Bs]) :- \+ succ(P, Q).

:- endif.

:- if(false).

bump(E, _, T, Bs, Bs) :- E =< T.
bump(E, P, T, [], [bump([P], [E])]) :- E > T.
bump(E, P, T, [bump([Q|Ps], [F|Es])|Bs], [bump([P,Q|Ps], [E,F|Es])|Bs]) :- E > T, succ(P, Q).
bump(E, P, T, [bump([Q|Ps], [F|Es])|Bs], [bump([P],[E]), bump([Q|Ps],[F|Es])|Bs]) :- E > T, \+ succ(P, Q).

:- endif.