Good afternoon. There was a question regarding the solution of this problem in the Prolog language:

Apply sorting by selection to the elements of a simple numerical list, starting with the k-th index and ending with the m-th.

It was possible to implement the sorting by choice. The lst predicate is used with the min_list and delete_one predicates .

I logically understand how this can be solved, but with the code I don’t roll into any code at all. I wanted to extract part of the string from the range and then shove it into the lst predicate, but I don’t understand how to work with ranges. The merge predicate is also implemented in case it is possible to sort a piece of string. The predicate of choice is sorting by selection in a range, but you can not pay attention here, because this part is not fully implemented.

Here is the code:

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).

I hope to help at least with cutting off part of the line from the specified range. Thank.

    1 answer 1

    To cut the first K elements from the list, you can use the predicate of the form:

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

    the first parameter is the number of elements to skip, the second is the original list, the third is the remaining elements, the fourth is the missing elements (needed for the subsequent concatenation)

    The last M elements can be skipFirst\4 predicate just entered:

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

    Sorting a sublist would then look like this:

     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).

    It remains to calculate K and M :

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

    Well, you need to handle the boundary conditions K and M

    • Thanks, used something similar, using the merge predicate, helped - Father Antelope