Пролог, чтобы проверить, отсортирован ли список (по возрастанию или по убыванию)

ProgramBox

Пролог, чтобы проверить, отсортирован ли список (по возрастанию или по убыванию)

Post author:admin
Запись опубликована:9 января, 2022
Post category:Вопросы по программированию

#sorting #prolog

Вопрос:

Я хочу написать предикат, который определит, отсортирован список или нет (по возрастанию или по убыванию оба вернут значение true).

 is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]):-X=<Y, is_sorted([Y|T]).

Это работает, когда я хочу проверить только один конкретный порядок, как я могу использовать его как для возрастания, так и для убывания?

1. Должен ли результат быть детерминированным?

2. да, так и должно быть

3. Вопрос не имеет никакого отношения к artificial-intelligence — пожалуйста, не спамьте нерелевантные теги (удалены).

Ответ №1:

Вы можете использовать compare/3 для создания экземпляра порядка (по возрастанию или по убыванию), как только в списке будет найдена первая пара отдельных смежных элементов.

 sorted(L) :- sorted(L, _).

sorted([], _).
sorted([_], _) :- !.
sorted([X,X|R], Order) :- !, sorted([X|R], Order).
sorted([X,Y|R], Order) :- compare(Order, X, Y), sorted([Y|R], Order).

Примеры:

 ?- sorted([ann, bob, coy]).
true.

?- sorted([coy, bob, bob, ann]).
true.

?- sorted([coy, bob, dan, bob, ann]).
false.

?- sorted([1, 2, 3, 3, 3, 4]).
true.

?- sorted([4, 3, 2, 1]).
true.

?- sorted([1-coy, 2-ann, 3-bob]).
true.

?- sorted([5-coy, 4-ann, 3-bob]).
true.

?- sorted([1-coy, 4-ann, 3-bob]).
false.

Ответ №2:

Вы можете передать предикат заказа в is_sorted .

 is_sorted(_, []).
is_sorted(_, [_]).
is_sorted(P, [X,Y|T]):- call(P, X, Y), is_sorted(P, [Y|T]).

Здесь P может быть любой предикат, принимающий два аргумента.

 ?- is_sorted(=<, [1, 2, 3, 4, 4]).
true 
?- is_sorted(<, [1, 2, 3, 4, 4]).
false.

?- is_sorted(>, [4, 3, 1, 0, -2]).
true 
?- is_sorted(@<, [hey, how]).
true 
?- is_sorted(@<, [hey, how, are]).
false.

Чтобы проверить, отсортирован ли список в порядке возрастания или убывания:

 sorted_any([]).
sorted_any([_]).
sorted_any([X, Y | T]) :-
    (X = Y) -> sorted_any([Y|T]);
    (
    (X < Y) -> is_sorted(=<, [Y|T]);
    is_sorted(>=, [Y|T])
    ).

1. спасибо, но здесь вы уже принимаете порядок, я пытаюсь написать предикат, который даст мне истину, если он отсортирован независимо от порядка, и ложь, если это не так

2. Вы можете использовать compare/3 для первых двух элементов списка, чтобы «заполнить» порядок (один из < , = , > ), а затем использовать этот порядок, чтобы проверить, находятся ли остальные элементы в том же порядке. сравнение/3 является более общим в том смысле, что оно определено для любых двух терминов пролога, поэтому вам не нужно беспокоиться @< < , например, о vs. Вам также не нужны никакие условия.

3. @User9213 : sorted([X,Y|T]) :- compare(O, X, Y), is_sorted(O, [Y|T]). , это идеально подходит для строгих заказов. =< >= Для или мне нужны условные условия.

4. @раджашекар хорошая мысль. Что происходит в вашем решении, если у вас есть набор равных элементов, за которыми следует что-то большее или меньшее? Например [a,a,a,b] , против [b,b,b,a] ?

5. @User9213 : Я думаю, что sorted_any преуспевает в обоих списках. У нас должно быть is_sorted(=<, [b]) и is_sorted(>=, [a]) на последней итерации, и то, и другое верно. Есть ли какие-то проблемы?

Ответ №3:

Обычно хорошей идеей является поиск решений, которые не требуют объединения более чем в начале и в конце списка. Это устраняет необходимость использования сокращений, чтобы не оставлять точки выбора открытыми во время оценки.

 sorted([]).
sorted([H|T]) :- sorted(T, H, _).

sorted([], _, _).
sorted([H|T], Last, Dir) :-
    compare(Dir1, H, Last),
    (   Dir1 = (=)
    ->  true
    ;   Dir1 = Dir),
    sorted(T, H, Dir).

Ответ №4:

Определить, отсортирован ли список в порядке возрастания, тривиально:

 ordered_ascending( []       ) .  % the empty list is ordered in ascending sequence.
ordered_ascending( [X]      ) .  % A list of length 1 is ordered in ascending sequence.
ordered_ascending( [A,B|Cs] ) :- % A list of length > 1 is ordered if...
  A @=< B ,                      % A is less than or equal to B, and
  ordered_ascending( [B|Cs] ) .  % the remainder of the list (less A) is similarly ordered.

Аналогично, определить, упорядочен ли список в порядке убывания, так же просто:

 ordered_descending( []       ) .  % the empty list is ordered in ascending sequence.
ordered_descending( [X]      ) .  % A list of length 1 is ordered in ascending sequence.
ordered_descending( [A,B|Cs] ) :- % A list of length > 1 is ordered if...
  A @>= B ,                       % A is greater than or equal to B, and
  ordered_descending( [B|Cs] ) .  % the remainder of the list (less A) is similarly ordered.

Добавьте оболочку, чтобы обеспечить необходимый детерминизм, и все готово:

 ordered( Xs ) :- ordered_ascending(  Xs ) , ! .
ordered( Xs ) :- ordered_descending( Xs ) , ! .

Вы можете сделать его более эффективным, добавив в обертку некоторые хитрости:

 ordered( []  ) .
ordered( [X] ) .
ordered( [X,Y|Zs] ) :- X @=< Y , ordered_ascending(  [Y|Zs] ) , ! .
ordered( [X,Y|Zs] ) :- X @>= Y , ordered_descending( [Y|Zs] ) , ! .

Вы заметите, что я отбрасываю здесь 1-й элемент списка, так как
нам не нужно проверять его снова.

Метки: отсортирован ли список (по возрастанию или по убыванию), ПРОЛОГ, чтобы проверить