序言：长度为k的子集

在我们过了subset_of/2谓词，我的老师给的类如下：序言：长度为k的子集

subset_of([],[]). 
subset_of([X|Xs],Zs):-subset_of(Xs,Ys),maybe_add(X,Ys,Zs). 

maybe_add(_,Ys,Ys). 
maybe_add(X,Ys,[X|Ys]). 

subsets_of(Xs,Xss):-findall(Ys,subset_of(Xs,Ys),Xss).

然后，他问我们将其更改为只给一些长度为K的子集（但不通过使用length/2，直接找到递归定义）。我的第一个尝试是将subset_of调用分解为一个添加额外元素和一个不调用（而不是具有maybe_add调用）的元素，并跟踪传递的列表长度并在最后检查，但这没有按计划运作。

subset_of(K, 0, [],[]). 
subset_of(K, Len, [X|Xs],Zs):- 
     L1 is Len - 1, 
     subset_of(K, L1, Xs, Zs), 
     L1 == K. 
subset_of(K, Len, [X|Xs],Zs):- 
     L1 is Len - 1, 
     subset_of(K, L1, Xs,Ys), 
     do_add(X, Ys, Zs), 
     Len == K. 
subsets_of(K,Xs,Xss):- 
     length(Xs, Len), 
     findall(Ys,subset_of(K, Len, Xs,Ys),Xss).

我不是要求正确的代码来解决这个问题，但只是在正确的方向推，所以我可以不断尝试弄清楚。这是我第一次用声明式的语言，我很困惑。

来源

2011-04-03 Stuart

如果你不想要一个直接的答案，比我说它可以做得简单得多。我的解决方案中有3条规则。但是，我不使用这个额外的maybe_add公式或其他任何可能的结果。如果你真的需要它，它可以被使用，然后它需要5个参数 - 3个输入参数和2个输出参数。与原始解决方案一样，这将subset_of的规则数量减少到只有2个。毕竟他们非常相似。

还要小心重复。我认为subset_of(0, _, [])正如其他答案中的建议可能是导致重复的一种方式。然而，可能有一个合并它的正确解决方案，我不确定没有。

认为它是正确性的证明。假设你想递归地证明一个集合是另一个集合的K元素子集。你将如何去做。看看你使用的含义。你怎么能把它们变成Prolog的规则？

来源

2011-04-03 21:05:49 julkiewicz

所以我想你所说的关于递归证明一个集合是另一个集合的一个k元素子集，这就是我所想到的。如果某物是k子集，那么如果你把第一个元素取出，其余的应该是一个k-1子集，它导致这个代码ksubset_of（0，_，[]）。 ksubset_of（K，[X |两个X]，ZS）： - K1为K1， \t \t \t ksubset_of（K1，XS，YS）， \t \t \t ZS = [X | YS〕.' 但这只会产生第一个，所以我不知道从哪里去 – Stuart 2011-04-03 22:42:12

这是好的，你已经有两个规则的候选人。然而，证明是不完整的，因此你错过了第三条规则。附注：不要写这样的统一'Zs = [X |伊苏]'。你应该把所有的'Zs'换成它的实际值。这不仅会更清晰，而且更高效。 – julkiewicz 2011-04-03 23:02:36

把它们想象成它们毕竟是有序的集合。这是因为他们被要求你的证明不完整。这就是我想说的，我想说的。 – julkiewicz 2011-04-03 23:10:56

不使用maybe_add似乎是一个好主意。然而，你不需要两个额外的参数：一个会做。您的基本子句将为

subset_of(0, _, []).

即，空集是任何东西的零元子集。在两个递归子句中，一个子查找K-1 -element子集，另一个查找K大小的子集。

来源

2011-04-03 20:48:06

序言：长度为k的子集

回答

相关问题