在 prolog 中查找列表的所有 k 长度子集 [英] find all k-length subsets of list in prolog

问题描述

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

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)

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

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

推荐答案

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

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

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

这篇关于在 prolog 中查找列表的所有 k 长度子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！