Как сделать сортировку вставками на Swi Prolog

Я хочу выполнить сортировку вставками, используя правила пролога swi. На данный момент мой код выглядит так:

isort([H|T],Sorted) :- T = [], Sorted = [H|T].

%When there are only two elements
isort([H1,H2|T],[H2,H1|T]) :- H1 > H2, T = [].
isort([H1,H2|T],[H1,H2|T]) :- H1 < H2, T = [].

%More than two elements
isort([H|T],Sorted) :- isort(T,Sorted).

Я пробовал все, но все это приводило меня в тупик и в конечном итоге сбивало меня с толку еще больше. Прямо сейчас, если я запрошу

isort([5,4,3,2,1],L).

он возвращается

L = [1,2].

Я не совсем понимаю, как другие номера не заботятся. Кто-нибудь, пожалуйста, развейте мое замешательство и, возможно, просветите меня, пожалуйста.


sorting declarative prolog insertion-sort
person Ryan Thompson    schedule 20.08.2018    source источник
comment
В isort([H|T],Sorted) :- isort(T,Sorted). вы никогда ничего не делаете с H.   -  person Steven    schedule 20.08.2018
comment
Я должен работать с ним? Я мог бы просто ввести isort([_|T],Sorted), чтобы игнорировать его.   -  person Ryan Thompson    schedule 20.08.2018
comment
Ну, если вы проигнорируете это, конечно, это не будет частью вывода.   -  person Steven    schedule 20.08.2018
comment
Ну, когда он включен, он выдает неправильный ответ.   -  person Ryan Thompson    schedule 20.08.2018
comment
Ваша первая проблема на самом деле заключается в том, что у вас нет рекурсии для обработки хвоста любого из ваших шаблонов. Помните, что T = [] в конце правила равносильно перезаписи головы с [] вместо T, поэтому ваше второе правило (например) становится isort([H1,H2], [H2,H1]) :- H1 > H2. Очевидно, вам нужно что-то делать с хвостом.   -  person Daniel Lyons    schedule 20.08.2018
comment
и isort([5,4,3,2,2],L). даже не вернет [2,2], а просто потерпит неудачу. isort([],L) тоже не работает.   -  person Will Ness    schedule 21.08.2018

Ответы (1)


arrow_upward
0
arrow_downward

Ваш код эквивалентен

isort([H],[H]).                 % a singleton list is sorted

isort([H1,H2],[H1 , H2]) :-     % an ascending list of two elts is sorted
               H1 < H2.    
isort([H1,H2],[H2 , H1]) :-     % a descending list of two elts is
               H2 < H1.         %  sorted, when reversed

isort([H|T],Sorted) :- isort(   % recursion... ?
         T ,Sorted           ).

Во-первых, как насчет isort([],[]).? Разве пустой список уже не отсортирован?

Во-вторых, как насчет isort([H1,H2],[H1 , H2]):- H1 =:= H2.? Разве список из двух одинаковых элементов уже не отсортирован?

Наконец, рекурсия. Как насчет фактического вставки вашего H в результат сортировки остальной части списка, T?

isort( [H|T],      S ) :-       % [H|T] sorted is       S, *if*
   isort( T,  TS ),             %    T  sorted is TS, *and*
   insert( H, TS,  S ).         % H inserted into TS is S

Теперь осталось только определить insert/3.

person Will Ness    schedule 21.08.2018
comment
Было ли это вообще полезно? Что-то еще непонятно? Не стесняйтесь спрашивать. - person Will Ness; 15.09.2018