根据偏好事实对键值对列表进行排序?
Sorting a list of key-value-pairs according to preference facts?
我有这个列表(从文件中读取):
[a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,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).
谓词 rank(In, Out) 使用 psort 作为 predsort 的谓词来根据偏好对我的列表进行排序。除了它没有。
输入:rank([a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,c-1,end_of_file], 排序).
实际输出:Sorted = [a-3, a-2, a-1, b-3, b-2, b-1, c-3, c-2, c-1, end_of_file].
预期输出:Sorted = [a-3, b-3, b-2, b-1, c-3, a-2, a-1, c-2, c-1, end_of_file].
输出不必是唯一的。对手头的任务重要的是偏好事实被考虑在内。
- 在序言中这样做是否可行?
- 我做错了什么?
- 什么是解决任务的有效替代方法(如 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).
下面的测试运行,仍然显示错误输出。那就是 'b-2' 永远不应该在 'b-3' 的左边,因为根据 gr(2) 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] .
关于效率:我把你的代码改成了
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 也会排除,以清理规范。如果无法更正输入 'routine',你可以做
?- 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-_).
...
我有这个列表(从文件中读取): [a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,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).
谓词 rank(In, Out) 使用 psort 作为 predsort 的谓词来根据偏好对我的列表进行排序。除了它没有。
输入:rank([a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,c-1,end_of_file], 排序).
实际输出:Sorted = [a-3, a-2, a-1, b-3, b-2, b-1, c-3, c-2, c-1, end_of_file].
预期输出:Sorted = [a-3, b-3, b-2, b-1, c-3, a-2, a-1, c-2, c-1, end_of_file].
输出不必是唯一的。对手头的任务重要的是偏好事实被考虑在内。
- 在序言中这样做是否可行?
- 我做错了什么?
- 什么是解决任务的有效替代方法(如 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).
下面的测试运行,仍然显示错误输出。那就是 'b-2' 永远不应该在 'b-3' 的左边,因为根据 gr(2) 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] .
关于效率:我把你的代码改成了
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 也会排除,以清理规范。如果无法更正输入 'routine',你可以做
?- 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-_).
...