Prolog Question - How to generate sublists of a given length
-
28-09-2019 - |
Question
I want to generate all the sublists of a given list with the given property that they have a certain length mentioned as argument and also they have as a containing element a given element which is passed as a parameter. I have managed to do this but with the help of two predicates, and in terms of optimality is very slow:
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).
In here I would like to return through the T
parameter of the choose
predicate all the sublists of the L list which have the dimension 2 or 1 and which contains the f
element.
The predicates dimension
and member
has the same usage as the predefined predicates length
, respectively member
.
Can you please tell me how to incorporate this two conditions within the sublist
predicate so that the program builds only those particular sublists?
Solution
The following builds subsequences of length MinLen =< Len =< MaxLen
. I've no idea why you renamed length
and member
, so I'm going to use the originals. sublist/4
calls your sublist/2
.
sublist(Sub,List,MinLen,MaxLen) :-
between(MinLen,MaxLen,Len),
length(Sub,Len),
sublist(Sub,List).
Note that length
is called on two variables, so you get an iterative deepening search. choose/2
can now be defined as
choose(Sub,List) :-
sublist(Sub,List,1,2),
member(f,Sub).
This is the clean solution. If it's is not fast enough, then roll all the conditions into one predicate:
choose(Sub,List),
(Sub = [f] ; Sub = [f,_] ; Sub = [_,f]),
sublist(Sub,List).