使用 length/2 和 ord_subset/2 生成子集 [英] Generating subsets using length/2 and ord_subset/2

问题描述

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

?- length(Lists, 3), ord_subset(Lists, [1, 2, 3, 4]).错误的.

期望获得所有长度为 3 的列表，这些列表是 [1, 2, 3, 4] 的子集，如 [1, 2, 3] 或 [1, 2, 4].为什么我是假的?

注意:length 和 ord_subset 都是 SWI-Prolog 中的内置函数(或它们的任何名称).

解决方案

你没有得到解决方案，因为 ord_subset/2 谓词只检查列表是否存在另一个列表的子集；它不会生成子集.

以下是一种定义谓词的简单方法，该谓词可以满足您的需求:

<预>子集集([]，_).subset_set([X|Xs], S) :-追加(_, [X|S1], S),subset_set(Xs, S1).

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

您会注意到子集恰好也是一个子序列.我们本可以这样写:

<预>subset_set(Sub, Set) :-% 前置条件(地面(设置))，% 前提条件( is_list(Set) ),% 前置条件( sort(Set, Set) ),subseq_list(Sub, Set).subseq_list([], []).subseq_list([H|T], L) :-追加(_, [H|L1], L),subseq_list(T, L1).

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

<预>?- 长度(子，3)，子集集(子，[1,2,3,4]).子 = [1, 2, 3] ;子 = [1, 2, 4] ;子 = [1, 3, 4] ;子 = [2, 3, 4] ;错误.

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

然而，第二个论点必须成立；如果不是:

<预>?- subset_set([A,B], [a,B]), B = a.A = B, B = a ;不是真正的套装，是吗?错误.

I am a beginner in prolog. I tried this in swipl interpreter:

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

expecting to get all length-3 lists that are subsets of [1, 2, 3, 4] like [1, 2, 3] or [1, 2, 4]. Why do i get false?

Notice: both length and ord_subset are builtin functions (or whatever they are called) in SWI-Prolog.

解决方案

You don't get a solution because the ord_subset/2 predicate only checks if a list is a subset of another list; it does not generate subsets.

Here is one simplistic way to define a predicate that does what you seem to be after:

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

This assumes that these are "ordsets", that is, sorted lists without duplicates.

You will notice that the subset happens to be also a subsequence. We could have written instead:

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

With either definition, you get:

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

You can even switch the order of the two subgoals in the example query, but this is probably the better way to write it.

However, the second argument must be ground; if it is not:

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

这篇关于使用 length/2 和 ord_subset/2 生成子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！