Сортировка списка пар ключ-значение в соответствии с данными предпочтений?

Question

У меня есть этот список (читайте в файле): [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). 

ранг сказуемое (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, end_of_file].

Ожидаемый результат: Сортировка = [a-3, b-3, b-2, b-1, c-3, a-2, a-1, c-2, c-1, end_of_file].

Выход не обязательно должен быть уникальным. Важное значение для этой задачи - учет данных предпочтений.

1. Возможно ли это сделать в прологе?
2. Что я делаю неправильно?
3. Что было бы эффективной альтернативой решению задачи (например, DAG, Topological-Sort, ...)?

EDIT

Используя полезные предложения от 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] . 

Answer 1

Об эффективности: Я изменил свой код

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

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

(срез означает, что нет никакого смысла изучает ЕЕ/2 соотношение, когда тот же самый первый элемент пара был замечен)

результат представляется целесообразным:

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

конечно, это сортируется от lower до высшее предпочтение. Просто повернуть его вспять, когда сделано, или поменять местами операторов в 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 из списка ввода, и ИПО/2 также, чтобы очистить спецификацию. Если это не представляется возможным, чтобы исправить ввод «рутинный», вы могли бы сделать

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

Фамилия, фо/2 кажется неполным (не с-3 предпочтительнее, чем-1? Я так думаю ...).Возможным простое решение может быть слева определено числовое поле:

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