Prolog. Сортировка списка в диапазоне от K до M

Question

День добрый. Возник вопрос по решению данной задачи по языку Prolog:

Применить сортировку выбором к элементам простого числового списка, начиная с k-го индекса и заканчивая m-ым.

Саму сортировку выбором реализовать удалось. Используется предикат lst с помощью предикатов min_list и delete_one.

Логически понимаю, как можно это решить, но с кодом вообще не катит ни в какую. Хотел извлечь часть строки из диапазона, а затем засунуть в предикат lst, но не понимаю, как работать с диапазонами. Предикат слияния тоже реализован, на случай, если получится отсортировать кусок строки. Предикат choice - сортировка выборкой в диапазоне, но можете не обращать сюда внимания, ибо эта часть не реализована до конца.

Вот код:

domains
i = integer
list = integer*
predicates
nondeterm min(i,i,i)
nondeterm delete_one(i, list, list)
nondeterm min_list(list, i)
nondeterm choice(i, i, list, list)
nondeterm lst(list, list)
nondeterm conc(list, list, list)
clauses
delete_one(_,[],[]).
delete_one(X,[X|L],L):-!.
delete_one(X,[Y|L],[Y|L1]):- delete_one(X,L,L1).

min(I,K,Res):- I<K, Res = I.
min(I,K,Res):- I>=K, Res = K.
min_list([X],X). 
min_list([H|T],M):- min_list(T,M_T), min(H,M_T,M). 

conc([], L, L).
conc([H|T], L, [H|T1]):- conc(T, L, T1).

choice(K, M, [], []):- K >= M, !.
choice(_, _, [], []):- !.
choice(K, M, List1, List2):-
conc(L1, [K|R], List1), 
conc(L2, [M|R], List1),
conc(L1, R, List2).

lst([],[]).
lst(L, [X|T]):- min_list(L,X), delete_one(X,L,L1), lst(L1,T).  
goal
%conc(L, [5|R], [1,2,3,4,5,6,7,8]).

%lst([2,3,1,8,4,5], Res).
%delete_one(5,[1,2,3,4,5], Res).
%min(1,2,Res).
%min_list([1,2,4,5,6,7,8],Res).
choice(3,8,[2,3,1,8,4,5], List).

Надеюсь, на помощь хотя бы с отсечением части строки из указанного диапазона. Спасибо.

score 0 · Accepted Answer · answered May 13 '19 at 04:44

Для отсечения первых K элементов от списка можно использовать предикат вида:

skipFirst(0,L,L,[]):- !.
skipFirst(K, [X|L], R, [X|S]):-
   N is K - 1,
   skipFirst(N, L, R, S).

первый параметр - число элементов, которые нужно пропустить, второй - исходный список, третий - оставшиеся элементы, четвертый - пропущенные элементы (нужен для последующей конкатенации)

Последние M элементов можно отсечь, использую только что введенный предикат skipFirst\4:

skipLast(0, L, L, []) :- !.
skipLast(K, L, R, S) :-
   reverse(L, Lrev),
   skipFirst(K, Lrev, Rrev, Srev),
   reverse(Rrev, R),
   reverse(Srev, S).

Сортировка подсписка тогда будет выглядеть так:

sortSublist(K, M, ListToSort, Result):-
   skipFirst(K, ListToSort, X, Sf),
   skipLast(M, X, Y, Sl),
   lst(Y, R),
   append(Sf, R, R1),
   append(R1, Sl, Result).

Остается вычислить K и M :

choice(K,M,L,R):-
   length(L, N),
   M1 is N - M,
   K1 is K-1,
   sortSublist(K1, M1, L, R), !.

Ну и нужно обработать граничные условия K и M

Спасибо, использовал примерно похожее, используя предикат слияния, помогло — FatherAntelope, May 13 '19 at 18:01

Prolog. Сортировка списка в диапазоне от K до M

1 Answers1