Пролог: как записать (и использование) функцию, которая перечисляет все перестановки списка?
Я нашел такой пример наивного вида записанным в прологе, и я пытаюсь понять это:
naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).
is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]):-X=<Y,is_sorted([Y|T]).
perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([],[]).
delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).
Вызов Naive_sort работает правильно, но я просто не могу выяснить почему. Основной проблемой является перестановка. Когда это называют неявно, это всегда возвращает только одно значение. Как затем возможно, что в naive_sort вызове функции все перестановки проверяются? Также, как я мог изменить функцию перманента для записи всех перестановок?
2 ответа
Это действительно наивная сортировка - - он просматривает дерево всех возможных перестановок, пока, к счастью, не найдет отсортированную. У этого есть сложность O (n!), Я полагаю:>
Что касается функции перестановки - она работает «в обратном направлении» - обратите внимание, что определение выводит голову из результата . Если вы перевернете свою точку зрения, вы заметите, что вместо удаления он фактически вставляет значения, работая в обратном направлении. Поскольку алгоритм работает в обратном направлении, то выбранным элементом H может быть что угодно, что позволит создать результат, а следовательно, любое неиспользуемое значение из списка.
В основном алгоритм перестановки преобразуется в следующую процедурную реализацию:
- выберите элемент из списка
- поместите его перед Sorted
Таким образом вы генерируете перестановки. Все они.
Короче говоря, perm генерирует все пространство возможных решений, начиная с пустого решения и проверяя, как данное решение возможно из действительного удаления.
?- perm( [ 1, 2, 3 ] , P )
P = [1, 2, 3];
P = [1, 3, 2];
P = [2, 1, 3];
P = [2, 3, 1];
P = [3, 1, 2];
P = [3, 2, 1];
no
Главная проблема - перестановка. Работать. Когда она называется неявно она всегда возвращает только одно значение.
Пролог - это язык, который всегда пытается доказать правдивость высказывания, выводя его с помощью приведенных аксиом (фактов или правил).
perm не является функцией в смысле процедурного программирования. perm - предикат, о котором мы говорим прологу две вещи:
- Пустой список - это перестановка самого себя.
List- это перестановка[H|Perm], если есть списокRestтак, чтоRestполучен путем удаленияHизList, аRest- это перестановкаPerm.
На вопрос, является ли один список перестановкой другого, пролог попытается применить эти шаги деривации (рекурсивно), чтобы доказать это. Если эта рекурсия заходит в тупик, т.е. утверждение, которое не может быть доказано, так как к нему не могут быть применены никакие правила, он отступает.