Select N elements from a List in Prolog

4
votes

I'm trying to write a Prolog predicate (SWI) that would select N elements from a List, like this:

selectn(+N, ?Elems, ?List1, ?List2) is true when List1, with all Elems removed, results in List2.

selectn(N,Lps,L1s,[]) :- length(L1s,L), N >= L, permutation(L1s,Lps).
selectn(0,[],L1s,Lps) :- permutation(L1s,Lps).
selectn(N,[E|Es],L1s,L2s) :- 
    select(E,L1s,L0s),
    N0 is N-1,
    selectn(N0,Es,L0s,L2s).

My problem is that in some cases, I get duplicated results and I don't know how to avoid them:

?- findall(L,selectn(2,Es,[a,b,c],L),Ls),length(Ls,Solutions).
Ls = [[c], [b], [c], [a], [b], [a]],
Solutions = 6.

This is no homework, but if you want to help me as if it was, I'll be pleased as well.

1
prolog

1 Answers

4
votes

this could answer your question (albeit I don't understand your first clause selectn/4, permutation is already done by 'nested' select/3)

selectn(0, [], Rest, Rest).
selectn(N, [A|B], C, Rest) :-
    append(H, [A|T], C),
    M is N-1,
    selectn(M, B, T, S),
    append(H, S, Rest).

yields

?- findall(L,selectn(2,Es,[a,b,c],L),Ls),length(Ls,Solutions).
Ls = [[c], [b], [a]],
Solutions = 3.