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).

我并不是要求正确的代码来解决这个问题，只是希望得到正确方向的指引，以便继续尝试解决它。这是我第一次接触声明式语言，感到非常困惑。

- Stuart

Answer 1

如果你不想要一个直接的答案，那么我会说它可以更简单地完成。我的解决方案中有3个规则。然而，我没有使用这个额外的maybe_add公式或任何类似的东西。如果你真的需要它，它可以被使用，并且它需要5个参数 - 3个输入参数和2个输出参数。这将减少subset_of的规则数量，只有2个，就像原始解决方案一样。它们非常相似。

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

把它看作正确性的证明。假设你想递归地证明一个集合是另一个集合的K元子集。你会怎么做？看看你使用的推论。你如何将它们转化为Prolog规则？

- julx

---

所以我思考了一下你关于递归证明一个集合是另一个集合的k元素子集的话，我想到了以下内容。如果某个东西是k子集，那么如果你把第一个元素拿出来，剩下的应该是一个k-1子集，这导致了这段代码 ksubset_of(0, _, []). ksubset_of(K, [X|Xs], Zs) :- K1 is K - 1, ksubset_of(K1, Xs, Ys), Zs = [X|Ys].但这只生成了第一个，所以我不知道该怎么做。 - Stuart

这是可以的，你已经有了两个规则的候选人。然而证明是不完整的，因此你缺失了第三条规则。附注：不要像这样写出统一的形式 Zs = [X | Ys]。你应该将所有的 Zs 替换为它的实际值。这不仅更清晰，而且更有效率。 - julx

把它们看作有序集合，因为它们本质上就是有序的。正是因为它们是有序的，所以你的证明才不完整。我想这就是我想说的。 - julx

啊，是的！在取出第一个元素后，有两件事情可以做：1.将k-1个子集添加到该元素中以获得k个子集，或者2.忽略它并从列表中生成k个子集。所以我的最终规则集是这样的ksubset_of(0, [], [])。 ksubset_of(K, [X|Xs], [X|Ys]) :- K1 is K - 1, ksubset_of(K1, Xs, Ys)。 ksubset_of(K, [X|Xs], Ys) :- ksubset_of(K, Xs, Ys)看起来正好按照预期工作。你说的第一条规则也会导致重复，所以我不得不进行了更改。感谢您的帮助，julkiewicz，我非常感激。 - Stuart

Answer 2

不使用maybe_add似乎是个好主意。然而，你并不需要两个额外的参数：一个就足够了。你的基本子句应该是

subset_of(0, _, []).

即空集是任何集合的零元子集。在这两个递归子句中，一个会寻找K-1元素的子集，另一个则寻找K大小的子集。

- Fred Foo