根据偏好事实对键值对列表进行排序？

Question

我有一个列表(从文件中读取)：a-3，a-2，a-1，b-3，b-2，b-1，c3，c-2，c-1，c-1，end_of_file

此外，我还有以下谓词：

% ipo(A,B) -> A is preferred over B
ipo(end_of_file, _).
ipo(c-3,a-3).
ipo(c-3,b-3).
ipo(c-3,b-2).
ipo(a-2,c-3).
ipo(a-2,b-2).

% gr(A,B) -> A is better than B | for example a-2 is better than a-3
% for same key, the lower value is better
% also A is better than B if A is preferred over B

gr(X-I, X-J):- I<J.
gr(A, B):- ipo(A,B).

psort(>, E1, E2):- gr(E1, E2).
psort(<, E1, E2):- \+ gr(E1, E2).

rank(In, Out):-
    predsort(psort, In, Out).

谓词秩(In，Out)使用psort作为predsort的谓词，对我的列表进行优先排序。但事实并非如此。

输入:等级(a-3，a-2，a-1，b-3，b-2，b-1，c-3，c-2，c-1，end_of_file，排序).

实际输出:排序= a-3，a-2，a-1，b-3，b-2，b-1，c-3，c-2，c-1，c-1，end_of_file.

预期输出:排序= a-3，b-3，b-2，b-1，c3，a-2，a-1，c-2，c-1，end_of_file.

输出不必是唯一的。对于手头的任务来说，重要的是考虑到偏好事实。

1. 在prolog中这样做可行吗？
2. 我做错什么了？
3. 什么是解决任务的有效替代方案(比如DAG，拓扑排序，.)？

编辑

使用CapelliC提供的有用建议，我成功地将我的程序推进到以下几个方面：

ipo(c-3,a-3).
ipo(c-3,b-3).
ipo(c-3,b-2).
ipo(b-1,c-3).
ipo(a-2,c-3).
ipo(a-2,b-2).

gr(X-I, X-J):- !, I<J.
gr(A, B):- ipo(A,B).

psort(>, E1, E2):- gr(E1, E2).
psort(<, _E1, _E2).

rank(In, Out):-
    predsort(psort, In, Out).

下面的测试运行，仍然显示错误的输出。因为根据gr(2)，b-2比b-3好，所以b-2永远不应该在b-3的左边。

?- combinations(L), append(L1, [_], L), rank(L1, Sorted).
L = [a-3, a-2, a-1, b-3, b-2, b-1, c-3, c-2, c-1, end_of_file],
L1 = [a-3, a-2, a-1, b-3, b-2, b-1, c-3, c-2, c-1],
Sorted = [a-3, b-2, c-3, a-2, a-1, b-3, b-1, c-2, c-1] .

Answer 1

关于效率:我已将您的代码更改为

gr(X-I, X-J):- !, I<J.
gr(A, B):- ipo(A,B).

psort(>, E1, E2):- gr(E1, E2).
psort(<, _E1, _E2).

(当看到相同的第一对元素时，裁剪意味着检验ipo/2关系是没有意义的)

结果似乎是适当的：

?- rank([c-3,a-2,a-3,a-1], Sorted).
Sorted = [a-3, c-3, a-2, a-1].

当然，它是从低到高的偏好。当操作完成时，只需将其反转，或者在psort/3中交换操作符：

psort(<, E1, E2):- gr(E1, E2).
psort(>, _E1, _E2).

?- rank([c-3,a-2,a-3,a-1], Sorted).
Sorted = [a-1, a-2, c-3, a-3].

我会将end_of_file排除在输入列表之外，并将ipo/2排除在外，以清理规范。如果无法更正输入“例程”，您可以这样做

?- append(L, [_], [c-3,a-2,a-3,a-1,end_of_file]).
L = [c-3, a-2, a-3, a-1]

最后，ipo/2似乎不完整(不是c-3比a-1更好吗？)我想是.)。一个可能的简单解决方案可能是保留未定义的数字字段：

ipo(c-_, a-_).
...