在序言中找到列表的所有k长度子集 [英] find all k-length subsets of list in 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并在新的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).

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