Пролог Поиск списков - PullRequest
Новая
       20

Пролог Поиск списков

6 голосов
/ 05 декабря 2011

Я пытаюсь сравнить списки.Данная функция (List1, List2) и List1 имеют длину N, а List 2 имеет длину M и N> M.

Я хочу проверить, не является ли какая-либо перестановка List2 первым M символами List1.

например, 

predicate([a,c,b,d,e],[a,b,c,d]).

должно быть истинным, а 

predicate([a,c,b,e,d],[a,b,c,d]).

должно быть ложным.

Спасибо.

Ответы [ 3 ]

4 голосов
/ 05 декабря 2011

Как часто при описании отношений между списками, в этом случае удобны DCG: 

perm_prefix(Ls1, Ls2) :- phrase(perm(Ls2), Ls1, _).

perm([])  --> [].
perm(Ls0) --> [L], { select(L, Ls0, Ls1) }, perm(Ls1).

Примеры случаев: 

?- perm_prefix([a,c,b,d,e],[a,b,c,d]).
true

?- perm_prefix([a,c,b,e,d],[a,b,c,d]).
false.
2 голосов
/ 08 ноября 2012

Вот еще одно решение DCG. 

perm(Xs,Ys) :- phrase(perm(Xs),[],Ys).

perm([])-->[].
perm([X|Xs])-->perm(Xs),ins(X).

ins(X),[X]-->[].
ins(X),[Y]-->[Y],ins(X).

Атрибуция: Моменты Пролога, экспонат 0

2 голосов
/ 05 декабря 2011

Используя предикаты permutation/2 и prefix/2, вы можете написать что-то вроде: 

has_prefix_perm(List1, List2) :-
    permutation(List2, Permutation),
    prefix(Permutation, List1),
    !.

В качестве примечания и цитаты Руководство по swi-прологу :

Обратите внимание, что список длины N имеет N! перестановки и генерация неограниченных перестановок становятся чрезмерно дорогими, даже для довольно коротких списков (10! = 3 628 800).

Так что я бы позаботился о том, чтобы не вызывать has_prefix_perm/2 со слишком длинным вторым списком, особенно если это не префикс по модулю перестановки, поскольку все случаи будут проверены.

Другим способом было бы проверить, являются ли элементы List1 членами List2, пока List2 не будет пустым, то есть вы знаете, что существует перестановка: 

has_prefix_perm(_, []) :- !.
has_prefix_perm([Head1|List1], List2) :-
    once(select(Head1, List2, Rest)),
    has_prefix_perm(List1, Rest).

Написано так, я бы не стал использовать его в неосновных списках, но, увидев ваш ОП, я не стал искать дальше ...

Другим способом было бы проверить, является ли List1, уменьшенный до длины List2, перестановкой List2: 

has_prefix_perm(List1, List2) :-
    length(List2, L),
    length(LittleL1, L),
    append(LittleL1, _, List1),
    permutation(LittleL1, List2),
    !.

Другим способом было бы ... Я думаю, есть много способов сделать это, просто выберите тот, который не является ужасной по сложности и подходит вашему стилю! :)

Я бы пошел с последним лично.

...