prolog:长度为 k 的子集

Question

在类里面，我们回顾了我的老师给出的 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).

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

Answer 1

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

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

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