Вопрос Пролога - Как генерировать подсписки заданной длины - PullRequest
Новая
       7

Вопрос Пролога - Как генерировать подсписки заданной длины

3 голосов
/ 04 ноября 2010

Я хочу сгенерировать все подсписки данного списка с заданным свойством, чтобы они имели определенную длину, указанную в качестве аргумента, а также в качестве содержащего элемента данный элемент, который передается в качестве параметра.Мне удалось сделать это, но с помощью двух предикатов, и с точки зрения оптимальности очень медленно: 

sublist([], []).
sublist([A|T], [A|L]):-
    sublist(T, L).
sublist(T, [_|L]):-
    sublist(T, L).

choose(T, L):-
    sublist(T, L),
    (dimension(2, T); dimension(1, T)),
    belongs(f, T).

Здесь я хотел бы вернуться через параметр T chooseпредикаты всех подсписков списка L, которые имеют размерность 2 или 1 и содержат элемент f.
Предикаты dimension и member используются так же, как и предопределенные предикаты length, соответственно member.

Подскажите, пожалуйста, как объединить эти два условия в * 1014?* предикат, чтобы программа строила только эти конкретные подсписки?

1 Ответ

2 голосов
/ 04 ноября 2010

Следующие строит подпоследовательности длины MinLen =< Len =< MaxLen. Понятия не имею, почему вы переименовали в length и member, поэтому я собираюсь использовать оригиналы. sublist/4 звонит вашему sublist/2. 

sublist(Sub,List,MinLen,MaxLen) :-
    between(MinLen,MaxLen,Len),
    length(Sub,Len),
    sublist(Sub,List).

Обратите внимание, что length вызывается для двух переменных, поэтому вы получаете итеративный углубляющий поиск . choose/2 теперь можно определить как 

choose(Sub,List) :-
    sublist(Sub,List,1,2),
    member(f,Sub).

Это чистое решение. Если это недостаточно быстро, объедините все условия в один предикат: 

choose(Sub,List),
    (Sub = [f] ; Sub = [f,_] ; Sub = [_,f]),
    sublist(Sub,List).
...