3

在课堂上，我们回顾了我的老师给出的 subset_of/2 谓词如下：

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 的子集（但不是通过使用长度/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).

我不是要求正确的代码来解决这个问题，而只是朝着正确的方向推进，这样我就可以继续尝试解决这个问题。这是我第一次使用声明性语言，我很困惑。

4

2 回答 2

1

如果您不想要直接的答案，那么我会说它可以做得更简单。我的解决方案中有 3 条规则。但是我不使用这个额外maybe_add的公式或任何重新排序它的东西。如果你真的需要它，可以使用它，它需要 5 个参数 - 3 个输入参数和 2 个输出参数。这将规则的数量减少subset_of到只有 2，就像在原始解决方案中一样。毕竟它们非常相似。

还要注意重复。我认为subset_of(0, _, [])正如其他答案中所建议的那样，可能是导致重复的一种方式。但是，可能有一个包含它的正确解决方案，我不确定是否没有。

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

于 2011-04-03T21:05:49.707 回答
0

不使用maybe_add似乎是个好主意。但是，您不需要两个额外的参数：一个就可以了。您的基本条款将是

subset_of(0, _, []).

即，空集是任何事物的零元素子集。在这两个递归子句中，一个会寻找K-1-element 子集，另一个寻找K-sized 子集。

于 2011-04-03T20:48:06.607 回答