Сортировка выбором в прологе

Я новичок в Прологе, и я пытаюсь сделать сортировку выбором. Вот что у меня есть:

ssort([],[]).
ssort([M|S],L):-min(M,L),remove(M,L,N),ssort(S,N).

min(M,[M]).
min(M,[H,T]):-min(N,T),min2(M,H,N).

min2(A,A,B):-less(A,B).
min2(B,A,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

Но когда я пытаюсь это, например:

ssort(S,[5,3,1]),write(S).

Я получаю false, как бы я ни старался. Можете ли вы сказать мне, как я могу отсортировать список и получить результат, записанный в S?


prolog program-slicing
person Petar D.    schedule 19.03.2017    source источник
comment
Вы проследили это? Вы сортируете первый или второй аргумент? Пробовали ли вы тестировать каждый из предикатов по отдельности? Например, вы уверены, что ваш min/2 делает то, что вы от него ожидаете? Я спрашиваю, потому что вы могли бы решить свою проблему самостоятельно без особых усилий, и потому что, если бы я попытался выполнить сортировку выбором в Прологе, это было бы слишком отлично от того, что у вас есть прямо сейчас, и это неприятная работа по выслеживанию чужих ошибок (багов).   -  person    schedule 19.03.2017
comment
К сожалению, я не знаю, как это отследить. Я сортирую второй аргумент и записываю результат в первый. min2 должен найти минимум между 2-м и 3-м аргументом и записать его в первый. Хотя я не уверен, что делаю это правильно :D   -  person Petar D.    schedule 19.03.2017
comment
Вот предложение: проверьте свои min/2 и min2/3. Если они работают так, как ожидалось, у вас есть проблема в другом месте (и кода не так много). Если они не работают должным образом, вы можете задать более узкий и конкретный вопрос, на который будет легче ответить. На данный момент у вас просто есть куча кода, и, пожалуйста, исправьте его, что не является хорошим подходом к вопросу.   -  person    schedule 19.03.2017
comment
независимо от того, что я пытаюсь сделать, вы пробовали ssort(S,[5]),write(S).? оно работает.   -  person Will Ness    schedule 19.03.2017

Ответы (2)


arrow_upward
4
arrow_downward

Как отметил @Boris, основная ошибка заключалась в предикате min/2, потому что ему нужен третий параметр, чтобы вернуть элемент min в этом параметре. С небольшими изменениями код выглядит так:

ssort([],[]).
ssort([M1|S],[H|T]):-min(H,T,M1),remove(M1,[H|T],N),ssort(S,N).

min(M,[],M).
min(M,[H|T],M1):-min2(M,H,N),min(N,T,M1).

min2(A,B,A):-less(A,B).
min2(A,B,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

Пример:

?- ssort(S,[5,3,1]).
S = [1, 3, 5] ;
false.

?- ssort(S,[5,3,1,7]).
S = [1, 3, 5, 7] ;
false.

ИЗМЕНИТЬ:

Как правильно указал @Will Ness, единственной ошибкой была запятая в min(M,[H,T]), поэтому изменение на min(M,[H|T]) работает нормально!!!. Я думал, что предикат min/2 работает не очень хорошо, поэтому я изменил его в ответе выше, но, в конце концов, в этом не было необходимости.

person coder    schedule 19.03.2017
comment
Что произойдет, если вы попробуете ssort(Sorted, [1,2,1])? - person ; 19.03.2017
comment
@Boris, я (уже) заметил, что когда есть повторяющиеся элементы, есть повторяющиеся ответы, например, ssort(Sorted, [1,2,1,1]) возвращает 6 одинаковых правильных ответов, потому что есть способы поставить три 1-элемента в начале отсортированного списка (3 способа для 1-й позиции, 2 для второго и 1 для третьего, так что всего 3 * 2 * 1 = 6 способов)... Я думаю, что это связано с предикатом min2/2, но в любом случае он не дает неправильных ответов... дубликаты можно удалить с помощью оператора cut... - person coder; 19.03.2017
comment
Спасибо за ответы. И последнее, почему вы называете предикат min min/2? - person Petar D.; 19.03.2017
comment
Рад помочь!!! Извините, я думал о первом предикате min с двумя параметрами, теперь это min/3 (/3 означает, что этот предикат имеет три параметра). - person coder; 19.03.2017
comment
не надо все это менять. все это было, была опечатка - всего лишь один неправильный символ в коде. может быть трудно заметить, визуально, тоже. - person Will Ness; 19.03.2017
comment
@ Уилл Несс, какой был всего один неправильный символ в коде ?? Я что-то упускаю?? - person coder; 19.03.2017
comment
запятая. я тоже поначалу пропустил. могу поклясться, что увидел там правильного персонажа. восприятие, управляемое ожиданием, да. - person Will Ness; 19.03.2017
comment
Давайте продолжим обсуждение в чате. - person Will Ness; 19.03.2017

arrow_upward
5
arrow_downward

Вот общий способ, как вы можете хотя бы локализовать ошибку в своей программе. Если ваш запрос не удался, просто удалите цели из своей программы. Если оставшийся фрагмент по-прежнему терпит неудачу, в этом фрагменте должна быть ошибка.

:- op(950,fy,*).
*_.

ssort(_/*[]*/,[]).
ssort(_/*[M|S]*/,L):-
   min(_/*M*/,L),
   * remove(M,L,N),
   * ssort(S,N).

min(M,[M]).
min(M,[H,T]):-
   * min(N,T),
   * min2(M,H,N).

?- ssort(S,[5,3,1]).

Поскольку этот фрагмент не работает, ваша исходная программа также не будет работать. Вам нужно что-то обобщить в оставшейся части.

person false    schedule 19.03.2017