Пролог, удаление надмножеств в списке списков

Допустим, у меня есть следующий список:

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

Поэтому мне было интересно, может ли кто-нибудь указать мне правильное направление, чтобы удалить все надмножества из списка или, может быть, даже дать правильный предикат.


list superset subset prolog
person fdorssers    schedule 05.12.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я использую 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.
person CapelliC    schedule 06.12.2012
comment
Большое спасибо, это было именно то, что нам было нужно. Нам следовало уделить больше внимания предикатам по умолчанию, потому что это хорошая реализация. - person fdorssers; 09.12.2012
comment
Вы неявно упомянули об этом, но это работает только для наборов, отсортированных по длине. - person Hendrikto; 20.10.2017

arrow_upward
0
arrow_downward

-Здравствуйте, Xylon, я думаю, что понял вашу идею, поэтому я попытался создать решение, используя эту идею. Вот он (дайте мне знать, подходит ли он вам или есть ошибки...)

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

%remove(ToRemove,ListWithSublists,LocRez,FinalRez)

Список %A из 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,LocRez,Final)

% удалить голову из списка из самого списка, если это необходимо (получить Rez в процессе)

%добавьте заголовок в наш 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),!.
person ssBarBee    schedule 06.12.2012
comment
Большое спасибо за ваше время и за создание решения. - person fdorssers; 09.12.2012