Prolog，如何对有约束的列表进行排序

Question

我对 Prolog 很陌生，我正在尝试使用它来排序具有定义约束的列表。

问题从以下定义开始：

Item 是长度为 3 的列表：[Name, Type, Weight]。
Content 是项目列表 [item_0,.....item_n]。
一个ContentList是Content

例如：

与项目：

item_1 = [chicken, meat, 1.0]
item_2 = [eggplant, vegetable, 0.5]
item_3 = [tomatoes, vegetable, 1.0]
item_4 = [bread, other, 0.2]

我们构建两个内容：

contentA = [item_2, item_3]
contentB = [item_1, item_4]
contentC = [item_3, item_4]

现在，假设我们有一些内容定义：

hasItemType([_, XType, _], XType).

hasListItemType([H|T], Type) :-
    hasItemType(H, Type);
    hasListItemType(T, Type).

hasListOnlyItemType([H|T], Type) :-
    hasItemType(H, Type),
    hasListItemType(T, Type)

isVegetarian(Content) :- hasListOnlyItemType(Content, vegetable).
hasVegetables(Content) :- hasListItemType(Content, vegetable).
hasMeat(Content) :- hasListItemType(Content, meat).

目标是：

给定一个 Content return 的列表，一个 ContentList 最匹配定义的顺序：

例如（但因此我的问题我不确定这样做是否正确。）

 -> `order(A, B)` A is before B in the output list.


order(ContentA, ContentB) :-
    isVegetarian(ContentA),
    hasVegetables(ContentB).

order(ContentA, ContentB) :-
    hasVegetables(ContentA),
    hasMeat(ContentB).

理想情况下，我想要这样的东西：

solve([contentB, contentC, contentA]) 会 return [contentA, contentB, contentC]

因为：顺序（contentA，contentB），顺序（contentA，contentC），顺序（contentB，contentC）

所以我基本上有两个问题：

这是形式化我的问题的合理方法吗？
一旦正确定义了order和约束条件，那么编写求解器的方法是什么？

我知道我的问题有点宽，所以我会采纳任何建议、参考、想法；）

如果您阅读本文，提前致谢！

Answer 1

您需要的是一个排序函数，但不是使用标准比较函数-谓词（如 =< 或 >= 进行排序，而是使用您的顺序谓词。所以需要在Prolog中实现一个排序算法，比如插入排序：

insertionSort([], []).

insertionSort([HEAD|TAIL], RESULT) :-
   insertionSort(TAIL, LIST), insertInPlace(HEAD, LIST, RESULT).

insertInPlace(ELEMENT, [], [ELEMENT]).

insertInPlace(ELEMENT, [HEAD|TAIL], [ELEMENT|LIST]) :-
   order(ELEMENT,HEAD), insertInPlace(HEAD, TAIL, LIST).

insertInPlace(ELEMENT, [HEAD|TAIL], [HEAD|LIST]) :-
   \+order(ELEMENT ,HEAD), insertInPlace(ELEMENT, TAIL, LIST).

您还可以实施效率更高的归并排序。由于我没有数据，所以我看不到上面的内容是否真的有效，或者它是否有一些错误，所以我正在等待评论...

我认为它有效我通过查询对其进行了测试：

insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).

我给出了一个列表 [content1,cntent2]，其中 content1 的类型是 meat，content 2 的类型是 vegetable 所以根据顺序谓词输出应该是 [content2,content1] 所以我认为输出是正确的：

?- insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).
Result = [[[eggplant, vegetable, 0.5], [tomatoes, vegetable, 1.0]], [[chicken, meat, 1.0], [beaf, meat, 1.0]]] ;
false.

Prolog，如何对有约束的列表进行排序

Prolog, how to order a list with constraints

prolog

constraint-programming