find all k-length subsets of list in prolog

问题:

i need to find a k-length subset of list in prolog, i have this function:

    subset([], []).
    subset([E|Tail], [E|NTail]):-
    subset(Tail, NTail).
    subset([_|Tail], NTail):-
    subset(Tail, NTail).

and i apply another rule for the length of the list,

    length(Xs,Size)

the problem is it is very slow because it search for all-length subset, is there a direct recursive definition for this k-length subset?

i searched for it for a week and cant find anything

回答1:

Using your initial solution to subset/2, you might add another argument (Len) and:

• Base case holds when Len = 0
• Recursive step which adds element decrements Len and finishes recursion if new Len=0

That would look:

 subset(0, [], []).
 subset(Len, [E|Tail], [E|NTail]):-
   succ(PLen, Len),
   (PLen > 0 -> subset(PLen, Tail, NTail) ; NTail=[]).
 subset(Len, [_|Tail], NTail):-
   subset(Len, Tail, NTail).