使用 length/2 和 ord_subset/2 生成子集

Question

我是 prolog 的初学者。我在 swipl 解释器中试过这个：

?- length(Lists, 3), ord_subset(Lists, [1, 2, 3, 4]).
false.

期望得到所有长度为 3 的列表，它们是 [1, 2, 3, 4] 的子集，例如 [1, 2, 3] 或 [1, 2, 4]。为什么我会报错？

注意：length 和 ord_subset 都是 SWI-Prolog 中的内置函数（或者它们的名称）。

Answer 1

您没有得到解决方案，因为 ord_subset/2 谓词仅检查列表是否是另一个列表的子集；它不生成子集。

这是定义谓词的一种简单方法，它可以完成您想要的事情：

subset_set([], _).
subset_set([X|Xs], S) :-
    append(_, [X|S1], S),
    subset_set(Xs, S1).

这假设这些是 "ordsets"，即没有重复的排序列表。

你会注意到子集恰好也是一个子序列。我们可以这样写：

subset_set(Sub, Set) :-
    % precondition( ground(Set) ),
    % precondition( is_list(Set) ),
    % precondition( sort(Set, Set) ),
    subseq_list(Sub, Set).

subseq_list([], []).
subseq_list([H|T], L) :-
    append(_, [H|L1], L),
    subseq_list(T, L1).

无论使用哪种定义，您都会得到：

?- length(Sub, 3), subset_set(Sub, [1,2,3,4]).
Sub = [1, 2, 3] ;
Sub = [1, 2, 4] ;
Sub = [1, 3, 4] ;
Sub = [2, 3, 4] ;
false.

您甚至可以在示例查询中调换两个子目标的顺序，但这可能是更好的编写方式。

但是，第二个参数必须接地；如果不是：

?- subset_set([A,B], [a,B]), B = a.
A = B, B = a ; Not a real set, is it?
false.

使用 length/2 和 ord_subset/2 生成子集

Generating subsets using length/2 and ord_subset/2

prolog

swi-prolog