1

假设我有以下列表：

List = [[a],[a,b],[a,c],[b,c],[b,d],[a,b,c],[a,b,d],[b,c,e],[b,d,e,f]]

目标是删除列表中作为列表中列表超集的每个列表。

包含列表的列表始终具有以下属性：

  • 列表中的列表按长度排序
  • 列表中的每个列表都已排序

我最初的想法是从列表中的第一个列表开始，然后遍历所有其他列表并删除作为超集的列表。接下来，我将查看第二个列表，等等。

删除列表 [a] 的所有超集后，它应该如下所示：

List = [[a],[b,c],[b,d],[b,c,e],[b,d,e,f]]

接下来应该删除 [b,c] 的超集：

List = [[a],[b,c],[b,d],[b,d,e,f]]

最后是 [b,d] 的超集：

List = [[a],[b,c],[b,d]]

上面的行应该是结果。

我已经创建了一个类似于成员谓词的谓词，但不是采用单个元素并将其与列表进行比较，而是采用整个列表并将其与列表进行比较：

memberList([],_).
memberList([X|Xs],Y) :-
    member(X,Y),
    memberList(Xs,Y).

这仅适用于列表。

?- memberList(a,[a,b,c]).
false.

?- memberList([a],[a,b,c]).
true .

?- memberList([a,b],[a,b,c]).
true .

但在这之后，我有点迷路了。

我尝试了以下应该删除单个集合的超集，但它不起作用：

removeSupersetsList(_,[],[]).
removeSupersetsList(X,[Y|Ys],[Y|Out]) :-
    not(memberList(X,Y)),
    removeSupersetsList(X,Ys,Out).
removeSupersetsList(X,[Y|Ys],Out) :-
    memberList(X,Y),
    removeSupersetsList(X,Ys,Out).

所以我想知道是否有人可以为我指出正确的方向，从列表中删除所有超集，或者甚至给出正确的谓词。

4

2 回答 2

0

-你好 Xylon，我想我理解你的想法，所以我尝试使用这个想法创建了一个解决方案。在这里（让我知道它是否适合您的需求，或者它是否有错误......）

memberList([],_).
memberList([X|Xs],Y) :-  member(X,Y),
                         memberList(Xs,Y).

%remove(ToRemove,ListWithSublists,LocRez,FinalRez)

%ListWithSublists 中的列表被删除，取决于 ToRemove

%LocRez 是用于获取 FinalRez 的累加器（最后）

remove(_,[],LocRez,LocRez) :- !.

remove(ToRemove,ListWithSublists,LocRez,FinalRez) :-     ListWithSublists=[Sublist|Rest],
                                                         memberList(ToRemove,Sublist),
                                                         remove(ToRemove,Rest,LocRez,FinalRez),!.

remove(ToRemove,ListWithSublists,LocRez,FinalRez) :-     ListWithSublists=[Sublist|Rest],
                                                         not(memberList(ToRemove,Sublist)),
                                                         append(LocRez,[Sublist],LocRezNew),
                                                         remove(ToRemove,Rest,LocRezNew,FinalRez),!.

removeSupersetsList(List,Rez) :- removeSupersetsList(List,[],Rez)。% 调用它进行测试

%removeSupersetsList（列表，LocRez，最终）

% 如果需要，从列表本身中删除列表中的头部（在此过程中获得 Rez）

% 将头部附加到我们的 LocRez（获取 LocRezNew）中，

% 递归调用 Rez

removeSupersetsList(List,LocRez,LocRez) :- List=[] ,!.
removeSupersetsList(List,LocRez,Final) :- ( List=[ToRemove|_] ; List=[ToRemove] ),
                                          remove(ToRemove,List,[],Rez),
                                          append(LocRez,[ToRemove],LocRezNew),
                                          removeSupersetsList(Rez,LocRezNew,Final),!.
于 2012-12-06T00:22:49.680 回答
0

我正在使用 SWI-Prolog，在那里我找到了一个为有序集制作的库和所需的测试，然后使用select /3 清理列表真的很容易

rem_super_sets([], []).
rem_super_sets([L|Ls], R) :-
    (   select(T, Ls, L1), % get any T in Ls
        ord_subset(L, T)   % is T a superset of L ?
    ->  rem_super_sets([L|L1], R) % discard T, keep L for further tests
    ;   R = [L|L2],
        rem_super_sets(Ls, L2)
    ).

这里有一个验证和结果

test :-
    List = [[a],[a,b],[a,c],[b,c],[b,d],[a,b,c],[a,b,d],[b,c,e],[b,d,e,f]],
    rem_super_sets(List, R),
    write(R).

?- test.
[[a],[b,c],[b,d]]
true.
于 2012-12-06T07:53:41.933 回答