1

次のリストがあるとします。

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

目標は、リスト内のリストのスーパーセットであるリスト内のすべてのリストを削除することです。

リストを含むリストには、常に次のプロパティがあります。

  • リスト内のリストは長さでソートされています
  • リスト内の各リストがソートされます

私の最初のアイデアは、リストの最初のリストから始めて、他のすべてのリストを調べて、スーパーセットであるリストを削除することでした。次に、2 番目のリストなどを見ていきます。

リスト [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)

%ToRemove に応じて、ListWithSublists からのリストが削除されます

%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(List,LocRez,Final)

%Remove the Head from List from the List自体から必要に応じて(プロセスでRezを取得)

%Head を LocRez(get 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 に答える