list - 在序言中找到列表的所有 k 长度子集

Question

我需要在 prolog 中找到一个长度为 k 的列表子集，我有这个功能:

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

我对列表的长度应用了另一条规则，

    length(Xs,Size)

问题是它很慢，因为它搜索全长子集，这个k长度的子集有直接的递归定义吗？

我找了一个星期都没找到

Answer 1

使用您对 subset/2 的初始解决方案，您可以添加另一个参数 (Len) 并且:

• 基本情况在 Len = 0 时成立
• 添加元素递减 Len 的递归步骤，如果新 Len=0 则完成递归

那看起来:

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