Обработка списка списков в Прологе

Question

Я новичок в Prolog и в логическом программировании в целом.Я пытаюсь попрактиковаться в учебнике, который у меня есть, и возник следующий вопрос: рассмотрим список списков, который выглядит, например, следующим образом:

[[spanish, white], [italian, white], [italian, red], [canadian, blue]]

Мы определим «гармонию» как набор уникальныхэлементы, которые расположены только в одном подсписке.Каждый индекс внутреннего списка представляет что-то вроде: национальность или цвет.Из приведенного выше примера [canadian, blue] - это «гармония», но [italian, white] - это не потому, что italian также в [italian, red].

Я пытаюсь создать отношение, которое перебирает подсписки ипытается создать лучшую "гармонию".Для примера выше, мы должны проверить первый подсписок;[spanish, white] и для каждого элемента проверьте, существует ли еще один подсписок, содержащий этот элемент.Если они уникальны, то это «гармония», в противном случае мы должны проверить, можем ли мы каким-то образом сократить один из этих списков.Выходные данные должны быть:

[[spanish, white], [italian, red], [canadian, blue]]

Объяснение: spanish подключен к white, поэтому мы не должны его трогать, но italian содержит оба с white и red.Тогда мы можем понять, что italian должен быть подключен к red, потому что white is with spanish`.

Конечная цель - получить список уникальных подсписков.Вы можете думать об этом как о системе уравнений, и мы хотим решить ее.

Другой пример:

[[spanish, white, 5], [italian, red,4], [canadian, blue,2],[canadian,red,2],[spanish, blue,4]]

Вывод:

 [[spanish, white, 5], [italian, red,4], [canadian, blue,2]]

Объяснение: давайте посмотримна [spanish, white, 5].Мы знаем, что spanish также находится в [spanish, blue,4], но blue находится также в [canadian, blue,2].canadian больше нигде не находится, поэтому blue принадлежит canadian.Это означает, что spanish получает white (а затем также 5).canadian получает 2, а это означает, что italian получает 4 и blue.

Я пытался использовать findall, но безуспешно.Я чувствую, что есть много информации, и это смущает меня.

Что было бы хорошим решением этой проблемы из учебника?

РЕДАКТИРОВАТЬ :

Всегда будет только одно возможное решение.если вы получили что-то вроде [[spanish, white], [italian, white]], то у вас нет никакой дополнительной информации, и вы должны оставить ее как есть.

Я пытался решить ее снова, но безуспешно.Я пытался как-то создать хеш-карту, которая будет содержать всю информацию, но мне кажется, что это не решение Prolog.Я думаю, что findall может решить это, но я не могу понять, как.

Answer 1

Как то так?

% Here is an interpretation of your defintion: For each List head (e.g. spanish,
% italian) select exactly one element from the input list. Then, check that the 
% selection is all in harmony. Please clarify if this is not the correct interpretation!

solution(List, Elements) :-
    select_all_heads(List, Elements),
    all_harmony(Elements).


% All elements (Elements) are in harmony when each of them (Element) is in 
% harmony with the rest (Others).

all_harmony([]).
all_harmony(Elements) :-
    foreach((member(Element, Elements),
             select(Element, Elements, Others)),
            harmony(Element, Others)).


% One sublist (Element) is in harmony with a list of other sublists (Others), if 
% it is either empty, or its Head is not contained in the heads of the other sublists
% (OthersHeads) and its tail (Tail) is also in harmony with the tails of the other
% lists (OthersTails).

harmony([], _).
harmony(Element, Others) :-
    Element=[Head|Tail],
    maplist(head_tail, Others, OthersHeads, OthersTails),
    \+ member(Head, OthersHeads),
    harmony(Tail, OthersTails).


% A list consists of a head (H) and a tail (T). This helper predicate can be used with maplist.

head_tail([H|T], H, T).


% Find all the heads, then select a member-sublist for each head.

select_all_heads(List, Elements) :-
    heads(List, Heads),
    select_all_heads(Heads, List, Elements).


% For each head element, select one sublist. Select the other heads from the rest.

select_all_heads([], _, []).
select_all_heads([Head|Heads], List, [Element|Elements]) :-
    select_head(Head, Element, List, List1),
    select_all_heads(Heads, List1, Elements).


% We need to know all the heads, so we know how many elements to select. 
% setof gives us a list without duplicates.

heads(List, Heads) :-
    setof(Head,
          T^member([Head|T], List),
          Heads).


% select one member (Element) of the input list (List) with a specific head (Head)
%  and leave the rest (Rest).

select_head(Head, Element, List, Rest) :-
    Element = [Head|_],
    select(Element, List, Rest).

Тест:

 ?- test1(L), solution(L, S).
  L = [[spanish, white], [italian, white], [italian, red], [canadian, blue]],
  S = [[canadian, blue], [italian, red], [spanish, white]] ;
false.

?- test2(L), solution(L, S).
  L = [[spanish, white, 5], [italian, red, 4], [canadian, blue, 2], [canadian, red, 2], [spanish, blue, 4]],
  S = [[canadian, blue, 2], [italian, red, 4], [spanish, white, 5]] ;
false.

Это не является оптимальным с точки зрения производительности, потому что нет промежуточного сокращения в наборе ответов, но это должно быть хорошо, чтобы проиллюстрировать Пролог.

Answer 2

Поскольку положение значений в подсписках фиксировано, и все подсписки заполнены:

harmony(As,Bs) :- maplist(dif,As,Bs).

harmonies(L,R) :-
    forall((select(A,L,S),member(B,S)), harmony(A,B))
    ->  R=L
    ;   select(_,L,T), harmonies(T,R)
    .

creasing_harmonies(L,R) :-
    setof(D-T,(harmonies(L,T),length(T,D)),R).

Не уверен, какой может быть «лучшая гармония». Предполагая, что это длиннее:

?- creasing_harmonies([[spanish, white, 5], [italian, red,4], [canadian, blue,2],[canadian,red,2],[spanish, blue,4]],L),last(L,B).
L = [1-[[canadian, blue, 2]], 1-[[canadian, red, 2]], 1-[[italian, red, 4]], 1-[[spanish, blue, 4]], 1-[[spanish, white|...]], 2-[[canadian|...], [...|...]], 2-[[...|...]|...], 2-[...|...], ... - ...|...],
B = 3-[[spanish, white, 5], [italian, red, 4], [canadian, blue, 2]].

Если у вашего Пролога нет dif / 2 или maplist / 3, аппроксимация может быть

harmony([],[]).
harmony([E|As],[E|Bs]) :- !, fail.
harmony([_|As],[_|Bs]) :- harmony(As,Bs).

редактировать

Пока что это очень неэффективно. Чтобы получить решение, необходимо уменьшить пространство поиска:

harmonies(L,R) :-
    length(L,N),N>4,
    (   forall((select(A,L,S),member(B,S)), harmony(A,B))
    ->  R=L
    ;   select(_,L,T), harmonies(T,R)
    ).

Но давайте посмотрим, сколько «решений» у нас есть сейчас

?- test_data(L),aggregate(count,harmonies(L,R),C).
L = [[table, green, alex, coffee, prince], [keyboard, green, alex, coffee, bookA], [keyboard, yellow, alex, water, bookA], [cup, red, alex, water, bookB], [computer, white, john, beer|...], [cup, red, birds|...], [keyboard, green|...], [keyboard|...], [...|...]|...],
R = [[table, green, alex, coffee, prince], [computer, white, john, beer, bookD], [cup, red, birds, milk, bookC], [keyboard, yellow, sabrina, water, bookA], [dane, blue, sasha, tea|...]],
C = 5040.

5040 дубликатов! Лучше остановиться на первом решении на фиксированной длине.

harmonies(L,N,R) :-
    length(L,M),M>=N,
    (   forall((select(A,L,S),member(B,S)), harmony(A,B))
    ->  R=L
    ;   select(_,L,T), harmonies(T,R)
    ).

?- test_data(L),harmonies(L,5,R).
L = [[table, green, alex, coffee, prince], [keyboard, green, alex, coffee, bookA], [keyboard, yellow, alex, water, bookA], [cup, red, alex, water, bookB], [computer, white, john, beer|...], [cup, red, birds|...], [keyboard, green|...], [keyboard|...], [...|...]|...],
R = [[table, green, alex, coffee, prince], [computer, white, john, beer, bookD], [cup, red, birds, milk, bookC], [keyboard, yellow, sabrina, water, bookA], [dane, blue, sasha, tea|...]] .