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

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

Ввод: rank([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].

Ожидаемый результат: Sorted = [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,...)?

ИЗМЕНИТЬ

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

sorting predicate prolog swi-prolog
person Toastgeraet    schedule 11.05.2016    source источник
comment
(1) да, (2) непонятно - вы показываете два фактических вывода, но ваш код дает только один (очевидно, правильный).   -  person lurker    schedule 11.05.2016
comment
(2) вы правы - я опечатался. Второй вывод, правильный, на самом деле то, что я ожидаю. Я изменил второе «фактическое» на «ожидаемое».   -  person Toastgeraet    schedule 19.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

Об эффективности: я изменил ваш код на

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 кажется неполным (разве с-3 не предпочтительнее, чем а-1? Наверное, да...). Возможным простым решением может быть оставить неопределенным числовое поле:

ipo(c-_, a-_).
...
person CapelliC    schedule 11.05.2016
comment
Да - ипо не обязательно полное. Собраны факты предпочтения, свободные от противоречий. Предполагается, что транзитивное замыкание должно учитываться моей логикой предикатов. Неполнота делает возможным существование нескольких допустимых решений бок о бок. - person Toastgeraet; 19.05.2016