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

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

Входные данные: ранг ([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. что было бы эффективной альтернативой решению задачи (например, DAG, Topological-Sort,...)?

EDIT

Используя полезные предложения от CapelliC i удалось продвинуть мою программу до следующего: 

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

Следующий тестовый запуск по-прежнему показывает ошибочные выходные данные. То есть "Б-2" никогда не должно быть слева от "Б-3", потому что согласно гр(2) Б-2 лучше, чем Б-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] .
1 2
sorting prolog

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-_).
...
2