gprolog - простой способ определить, является ли один список перестановкой другого
Я пытаюсь написать прологическую программу, которая определяет, является ли один список перестановкой другого. Вход имеет вид perm(L,M), который будет истинным, если и только если список L перестановка списка M,
Это для моего класса AI, поэтому я не могу просто использовать изящный маленький permutation Предикат, который gprolog уже предоставляет. Наш профессор отметил, что member Предикат может быть полезен, но любые идеи, которые у меня есть, включают в себя, кажется, требующие очень хитрых и не столь декларативных вещей (и я предполагаю, что есть способ решить эту проблему, не становясь слишком продвинутым, так как класс является новым для пролога.)
В любом случае, один из способов проверить это предположительно L а также M одинакового размера, каждый L элемент находится в Mи каждый M элемент находится в L (есть использование member!). Однако этого будет недостаточно для таких случаев, как [2,2,4] а также [4,4,2]среди других.
Другим способом может быть обеспечение того, чтобы одинаковые значения каждого элемента были в противоположном списке, но у меня сложилось впечатление, что любой вид переменной "память" довольно сложный бизнес (на самом деле, кажется, что примеры программ, которые я вижу, выполнять сортировки и т. д., на самом деле вообще не манипулируют данными, они просто "гипотетически" перестраивают вещи и затем говорят вам, да или нет...?)
Мысленно можно просто отсортировать оба списка и проверить элементы рядом, но это, среди множества других способов думать об этом, кажется немного слишком объектно-ориентированным...
Есть намеки? Похоже, моей самой большой проблемой (как уже упоминалось) является то, что выполнение "операций" больше похоже на расспросы о них и надежду, что все останется верным достаточно долго, чтобы добраться туда, куда вы хотите.
** ОБНОВЛЕНИЕ: gprolog предлагает delete функциональность, но это связано с декларативной проблемой, которую я ожидал, учитывая такую попытку:
perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).
В руководстве удаление определяется следующим образом: "delete(List1, Element, List2) удаляет все вхождения Element в List1 для предоставления List2. Требуется строгое равенство, ср. (==)/2"
Исполнение:
{trace}
| ?- perm([1,2,3],[3,1,2]).
1 1 Call: perm([1,2,3],[3,1,2]) ?
2 2 Call: member(1,[3,1,2]) ?
2 2 Exit: member(1,[3,1,2]) ?
3 2 Call: delete([1,2,3],1,[3,1,2]) ?
3 2 Fail: delete([1,2,3],1,[3,1,2]) ?
2 2 Redo: member(1,[3,1,2]) ?
2 2 Fail: member(1,[3,1,2]) ?
1 1 Fail: perm([1,2,3],[3,1,2]) ?
(1 ms) no
** ОБНОВЛЕНИЕ 2: я думаю, что я мог понять это! Это довольно многословно, но я проверял это довольно много случаев и пока не нашел плохого. Если кто-то видит серьезную проблему, пожалуйста, укажите на это:
perm([],[]).
perm([LH|LT],R) :- length([LH|LT],A), length(R,B), A == B, member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
perm_recurse([],X). %If we get here, all elements successfully matched
perm_recurse([LH|LT],R) :- member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
Мне нравится оператор вырезать..
4 ответа
Всегда хорошо определить более общий предикат и использовать его в узком смысле:
perm(X,L):- mselect(X,L,[]).
mselect([A|B],L,R):- select(A,L,M), mselect(B,M,R).
mselect([],L,L).
member не годится, так как оставляет второй список без изменений. delete тоже не годится, так как удаляет кратности.
Вы могли бы использовать append хоть.:) Это тоже сочетает в себе сбор и удаление:
perm([A|B],L):- length(L,N), between(0,N,I),length(X,I),
append(X,[A],Y), append(Y,Z,L),
append(X,Z,M), perm(B,M).
perm([],[]).
perm(L, M) :- sort(L, X), sort(M, X).
Это очень близко подходит для вас и является полностью декларативным ("два списка являются перестановками друг друга, если они имеют одинаковое отсортированное представление", но сортировка в Прологе удаляет дубликаты). Тем не менее, это удастся для таких случаев, как perm([1,2], [2,2,2,1]) что я не уверен, если вы хотите. Он будет обрабатывать [2,2,4] и [4,4,2], так как они оба сортируют [2,4], Другое решение будет примерно таким:
perm([], []).
perm([L|Ls], M) :- select(L, M, Ms), !, perm(Ls, Ms).
Эта версия не будет успешной для [2,2,4] и [4,4,2], но она будет некорректно работать для [1,2] и [2,2,2,1]. Я не уверен, какой вы хотите, но я думаю, что один или другой из них, вероятно, правильно.
Обычная модель для подражания является индуктивной.
Если вы знаете, как построить всю перестановку из N-1 элементов, то все перестановки из N элементов получаются, вставляя элемент во все доступные позиции.
"Уловка сделки" использует встроенную функцию select/3, которая, подобно элементу, "просматривает" элемент, но удаляет его из списка и "возвращает" меньший список. Эти глаголы не совсем подходят для Пролога. Допустим, что select/3 - это отношение между элементом, списком, содержащим его, и идентичным списком, в котором он отсутствует.
Тогда пусть Пролог сделает весь поиск... Полученный код действительно крошечный...