次のリストがあるとします。
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).
だから、誰かが私を正しい方向に向けて、リストからすべてのスーパーセットを削除したり、正しい述語を与えたりできるかどうか疑問に思っていました.