发现列表的所有K-长度子集在序言

我需要找到在序言列表的K-长度子集，我有这个功能：发现列表的所有K-长度子集在序言

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

，我申请的另一个规则的长度列表，

length(Xs,Size)

问题，是因为它搜索所有长度的子集，它是非常缓慢的，是有这个K-长度子集的直接递归定义？

我搜索了一个星期，并不能找到任何

来源

2013-04-05 Dima

我的意思是（抱歉，如果它看起来smartassing）什么是你应该尝试自己，展现你做了什么，什么是不为你工作... – gusbro 2013-04-05 14:45:15

我想这一点，但它不能正常工作，subset_of （K，0，[]，[]）。（K，Len，[X | Xs]，Zs）： L1是Len_1, subset_of（K，L1，Xs，Zs）， L1 == K. 012-subset_of （X，Ys，Zs）： L1 = K. 子集的（K，Xs，Zs）：子集（K，Xs，，Xss）： - length（Xs，Len）， findall（Ys，subset_of（K，Len，Xs，Ys），Xss）。 – Dima 2013-04-05 14:49:47

保持计数记录的想法是正确的，但不需要使用findall。查看对原始子集程序的简单修改的答案 – gusbro 2013-04-05 15:11:17

使用您最初的解决方案subset/2，您可以添加另一种说法（LEN）和：

基本情况成立时，莱恩= 0
这增加了元件的递归步骤递减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).

来源

2013-04-05 15:03:31 gusbro

它看起来不错，但由于某些原因，它不会更快：\ – Dima 2013-04-05 15:52:32

您可以将第一个子句更改为“subset（0，_，[]）： - ！。”，就像Len为零无论输入列表如何，结果都必须是空列表......不知道它是否真的可以显着提高性能。 – gusbro 2013-04-05 16:02:56

仍然是相同的速度.... – Dima 2013-04-05 16:24:12

发现列表的所有K-长度子集在序言

回答

相关问题