list - 在 prolog 中查找列表的所有 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 并在 new 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).