CODEWITHSUNDEEP
sortingprologpredicateswi-prolog
Toastgeraet
Toastgeraet

Reputation: 371

Sorting a list of key-value-pairs according to preference facts?

I have this list (read from a file): [a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,c-1,end_of_file]

Also i have the following predicates:

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

The predicate rank(In, Out) uses psort as a predicate for predsort to sort my list for preference. Except it doesn't.

The input: rank([a-3,a-2,a-1,b-3,b-2,b-1,c-3,c-2,c-1,end_of_file], Sorted).

The actual output: Sorted = [a-3, a-2, a-1, b-3, b-2, b-1, c-3, c-2, c-1, end_of_file].

The expected output: Sorted = [a-3, b-3, b-2, b-1, c-3, a-2, a-1, c-2, c-1, end_of_file].

The output does not have to be unique. Important to the task at hand is the the preference facts are accounted for.

  1. Is it feasible to do this in prolog?
  2. What am i doing wrong?
  3. What would be an efficient alternative to solving the task (like DAGs, Topological-Sort, ...) ?

EDIT

Using the helpful suggestions from CapelliC i managed to advance my program to the following:

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

The following test run, still shows erroneous output. That is 'b-2' should never be to the left of the 'b-3' because according to gr(2) b-2 is better than 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] .

Upvotes: 2

Views: 662

Answers (1)

CapelliC
CapelliC

Reputation: 60014

About efficiency: I've changed your code to

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

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

(the cut means there is no point is examining the ipo/2 relation, when the same first element of pairs has been seen)

The outcome seems appropriate:

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

Of course, it's sorted from lower to higher preference. Just reverse it when done, or swap the operators in 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].

I would exclude end_of_file from the input list, and ipo/2 also, to clean up the specification. If it's not possible to correct the input 'routine', you could do

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

Last, ipo/2 seems incomplete (isn't c-3 preferred over a-1 ? I guess so...). A possible simple solution could be to left undefined the numeric field:

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

Upvotes: 2

Related Questions