时间戳

首页 > 解决方案 > Prolog：集合和操作

list - Prolog：集合和操作

问题描述

我正在 prolog 中开发谓词来操作集合。我正在尝试使用以下内置预测来实现 3 个谓词：member/2、append/3、length/2、permutation/2：

1) list_to_set/2

将列表转换为集合的谓词。给定列表Xs = [1, 2, 3, 3]，我需要返回Xs没有重复的排列。

输入

?- list_to_set([3, 1, a, a], Es).

输出

?- Es = [1,3,a];
?- Es = [1,a,3];
?- Es = [3,1,a];
?- Es = [3,a,1];
?- Es = [a,1,3];
?- Es = [a,3,1].

2) 联合/3

给定两组 Xs，Rs。谓词Union(Xs, Rs, Es)检查是否是 set和Es之间的并集。XsRs

输入

?- union([2,1,3,a], [4,1,3,a], Es).

输出

?- Es = [1,3,a];
?- Es = [1,a,3];
?- Es = [3,1,a];
?- Es = [3,a,1];
?- Es = [a,1,3];
?- Es = [a,3,1].

4) 差异/3

给定两组 Xs，Rs。谓词Diff(Xs, Rs, Es)检查是否是 set和Es之间的差异。XsRs

输入

?- diff([2,1,3,a], [4,1,3,a], Es).

输出

?- Es = [2, 4];
?- Es = [4, 2].

这是我到目前为止所做的：

%list to set predicate
list_to_set(Xs , Cs) :-
  lpc(Xs, [], Cs).

lpc([], Rs, Rs).
lpc([X | Xs], Rs, Cs):-
    member(X, Rs),
    lpc(Xs, Rs, Cs).
lpc([X | Xs], Rs, Cs):-
    lpc(Xs, [X|Rs], Cs).

%union between two sets predicate
union([], _, _).
union([C|Cs], Ds, Es) :-
    member(C, Ds),
    union(Cs, Ds, Es).
union([C|Cs], Ds, [C|Es]) :-
    member(C, permutation(Cs, Es)),
    union(Cs, Ds, Es).

diff([], _, []).
diff([C |Cs], Ds, Es):-
    member(C, Ds),
    diff(Cs, Ds, Es).
diff([C | Cs], Ds, [C | Es]):-
    member(C, permutation(Cs, Es)),
    diff(Cs, Ds, Es).

伙计们，我如何调整上面的代码以使用排列？我尝试了各种实现，但没有一个有效。

标签： listprologsetpermutation

解决方案

  1. 要设置的列表

     list_to_set([], []).

 list_to_set([H|T], Z):-
     member(H,T),
     list_to_set(T, Z1),!,
     permutation(Z1,Z).

 list_to_set([H|T], Z):-
     not(member(H,T)),
     list_to_set(T, Z1),!,
     append([H], Z1, Z2),
     permutation(Z2,Z).

2）联合

警告：这不是设置联合操作，它更像是交集（代码基于您的示例）。 
    union([],_,[]).
    union([H|T], L2, Es):-
        union(T, L2, Z1),
        (member(H, L2) -> append([H],Z1,Z2) ; Z2 = Z1),!,
        list_to_set(Z2, Es).

3）
差异警告：这不是设置差异操作，它更像是对称差异（再次，代码基于您的示例）。 
    diff(L1, L2, Es):-
        append(L1,L2,L3),
        union(L1,L2,L4),!,
        subtract(L3,L4,L5),
        list_to_set(L5,Es).

如果不能使用减法谓词，定义自己的实现并不困难。

推荐阅读