Пролог: как написать (и использовать) функцию, которая перечисляет все перестановки списка?

Question

Я нашел такой пример наивного рода, написанный на прологе, и я пытаюсь его понять:

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 проверяются все перестановки? Также, как я могу изменить функцию perm для записи всех перестановок?

Answer 1

Основная проблема - перестановка функция. Когда это называется неявно всегда возвращается только одно значение.

Пролог - это язык, который всегда пытается доказать истинность утверждения, выводя его, используя приведенные аксиомы (факты или правила).

perm не является функцией в смысле процедурного программирования. perm - это предикат, о котором мы говорим прологу две вещи:

1. Пустой список - это перестановка.
2. List - это перестановка [H|Perm], если существует список Rest, такой, что Rest получается путем удаления H из List, а Rest - это перестановка Perm.

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

Answer 2

Это действительно наивный вид - он пересекает дерево всех возможных перестановок, пока, к счастью, не находит отсортированный. Это сложность O (n!) Я предполагаю:>

Насчет функции перестановки - она ​​работает "в обратном направлении" - обратите внимание, что определение выводит голову из результата . Если вы перевернете свою точку зрения, вы заметите, что вместо удаления она фактически вставляет значения, работая в обратном направлении. Поскольку алгоритм работает в обратном направлении, следовательно, выбранный символ H может быть любым, что позволит создать результат, а следовательно, и любым неиспользованным значением из List.

В основном алгоритм перестановки переводится в следующую процедурную реализацию:

1. выбрать предмет из списка
2. положить его перед отсортированным

Таким образом, вы генерируете перестановки. Все они.

Вкратце - 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

Answer 3

используйте точку с запятой (;) в конце каждой перестановки, которую пролог даст вам до тех пор, пока не будет другой перестановки, пролог должен сказать Нет