CODEWITHSUNDEEP
prologbacktracking
Simon
Simon

Reputation: 5039

Prolog Question - How to generate sublists of a given length

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?

Upvotes: 3

Views: 2780

Answers (1)

Fred Foo
Fred Foo

Reputation: 363828

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).

Upvotes: 2

Related Questions