Помогите решить задачку о нахождении всех перестановок элементов списка на прологе? Это не для вуза, для самообразования. Долго пытался, но не смог. Что-то важное не могу постичь.
DOMAINS
list = integer*
PREDICATES
permutations(list, list)
Например, для permutations([1,2,3], X) должен вывести (не обязательно в таком порядке):
X=[1,2,3]
X=[1,3,2]
X=[2,1,3]
X=[2,3,1]
X=[3,1,2]
X=[3,2,1]
Здравствуйте, Juster, Вы писали:
J>Помогите решить задачку о нахождении всех перестановок элементов списка на прологе? Это не для вуза, для самообразования. Долго пытался, но не смог. Что-то важное не могу постичь.
Можно пойти по определению:
permutation(Xs,Ys) отвечает на вопрос: является ли Xs перестановкой Ys (и наоборот).
Обрати внимание на характер постановки задачи. Это не функция permutations : *int -> **int, возвращающая список списков (все перестановки), а предикат, "возвращающий" одну перестановку. Перебор осуществляется откатами.
Это фундаментальное отличие логического программирования от, например, функционального. (Хотя, разумеется, ФП можно выразить через ЛП и наоборот).
permutation(X,X). % идентичная перестановка
permutation([X|Xt],[X|Yt]) :- permutation(Xt,Yt). % если совпадают головы, то нужно проверить перестановку хвостов
permutation([X|Xt],[Y|Yt]) :-
extract(Yt,X,Zt), % Zt = Yt \ [X]
permutation(Xt,[Y|Zt]).
Тут видно, что последние два клоза (да, в общем-то, и первый) можно объединить — какая разница, извлекать со второй позиции, или с первой
Единственно, нужно убедиться, что предикаты имеют "обратную силу", т.е. способны не только проверять, но и порождать все возможные факты (без повторений!).
Здравствуйте, Кодт, Вы писали:
К>Можно пойти по определению: К>permutation(Xs,Ys) отвечает на вопрос: является ли Xs перестановкой Ys (и наоборот). К>Обрати внимание на характер постановки задачи. Это не функция permutations : *int -> **int, возвращающая список списков (все перестановки), а предикат, "возвращающий" одну перестановку. Перебор осуществляется откатами. К>Это фундаментальное отличие логического программирования от, например, функционального. (Хотя, разумеется, ФП можно выразить через ЛП и наоборот).
К>
К>permutation(X,X). % идентичная перестановка
К>permutation([X|Xt],[X|Yt]) :- permutation(Xt,Yt). % если совпадают головы, то нужно проверить перестановку хвостов
К>permutation([X|Xt],[Y|Yt]) :-
К> extract(Yt,X,Zt), % Zt = Yt \ [X]
К> permutation(Xt,[Y|Zt]).
К>
К>Тут видно, что последние два клоза (да, в общем-то, и первый) можно объединить — какая разница, извлекать со второй позиции, или с первой К>
К>Единственно, нужно убедиться, что предикаты имеют "обратную силу", т.е. способны не только проверять, но и порождать все возможные факты (без повторений!).
Большое спасибо, заставили думать.
Мне кажется, что задачи в прологе как и в императивных языках проще решать сверху, сначала описываем как будет решаться задача, а потом опускаемся по уровню вплоть до самых простых предикатов.
У меня проблема в решении задач состоит в преодолении какого-то барьера... бывает не могу решить задачу (а решаю я только обучающие задачи из головы и всяких книжек), а посмотрю решение и все понятно...
К>Пример: очевидно, что К>
Но самое главное, что предикат permutation не выполняется, т.к. при просмотре первого определения extract, Xt — не bound. Если продолжить, несмотря на замечание, то heap overflow.
К>>при запросе equalLists([1,2,3],Ys) даст 8 одинаковых ответов Ys=[1,2,3] J>Не понял, что из этого следует?
Из того, что оба клоза дают одинаковый ответ.
Если мы напишем запрос с циклом
?- equalLists([1,2,3],Ys), write(Ys), fail. % чтобы перебрать и вывести все варианты
то увидим.
Достаточно потрассировать, чтобы убедиться.
Только я ошибся: не 8, а 4. Потому что для пустого списка подходит только первый клоз, поэтому общее число вариантов — 2^(n-1) где n — длина списка.
Не просто достаточно, но и необходимо!
J>Но самое главное, что предикат permutation не выполняется, т.к. при просмотре первого определения extract, Xt — не bound. Если продолжить, несмотря на замечание, то heap overflow.
Вот как раз об этом я и говорил. И, похоже, сам наступил на грабли Предикат умеет проверять, но не умеет выводить.
А ещё
permutation([], []). % забыл вот это. без него рекурсия не пройдёт.
Сейчас подумаю, как рекуррентный предикат определить.
Стоит различать перестановки уникальных и неуникальных элементов.
Разница в том, что в первом случае мы получаем ровно N! перестановок N-элементных наборов, а во втором — можем получить меньше.
И если у нас уникальность формальная, т.е. мы не занимаемся сравнениями элементов, то скормив такому алгоритму на вход набор с дублями, получим дубли наборов.
Алгоритм, который ты привёл — именно такой.
Важный момент — определение эквивалентности.
Если эквивалентность определена через порядок (x=y <=> ~(x<y)&~(y<x)), то можно воспользоваться алгоритмом Кнута next_permutation, порождающим лексикографически упорядоченную последовательность перестановок. Для чисел это очень естественно.
Если же эквивалентность дана сама по себе, то придётся повыкручиваться.
Возможное решение — отобразить список "чего попало" на список целых чисел и дальше использовать алгоритм Кнута.
Перекуём баги на фичи!
Предикат умеет проверять, но не умеет выводить.
