prolog - 处理 Prolog 中的列表列表

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, 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可能会解决它，但我似乎无法弄清楚如何。

标签： prolog

Answer 1

由于子列表中值的位置是固定的，并且所有子列表都是完整的：

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

如果您的 Prolog 没有 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|...]] .