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

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

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 для записи всех перестановок?

Источник

3 ответа

Решение

Это действительно наивный вид - он пересекает дерево всех возможных перестановок, пока, к счастью, не находит отсортированный. Это сложность 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
Источник

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

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

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

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

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

Источник

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

Источник
Другие вопросы по тегам