CODEWITHSUNDEEP
listsortingprolog
Pl4n7
Pl4n7

Reputation: 31

Prolog: Sort a list by alternative index

I'm attempting to sort a list of colors, by a given preffered order. For example a list [r,z,z,w,g,g,r,z] sorted in this order [z,b,g,r,w], will give an end result of [z,z,z,g,g,r,r,w].
I tried using a basic bubblesort algorithme and adding a check to see which of first two terms would be 'higher' on the order list. 

% take the to-sorted list, the order in which to sort the list, and the
% result. 
%colourSort([r,z,z,w,g,g,r,z],[z,b,g,r,w],X). returns X = [z,z,z,g,g,r,r,w]

colourSort(List,Order,Sorted):-
    swap(List,List1,Order),
    !,
    colourSort(List1,Order,Sorted).

colourSort(Sorted,_,Sorted).

% check if the either the first or second letter is first in the order
% list, if neither check the next letter in the order list. 
check(A,_,[H|_],A):-
    A == H.
check(_,B,[H|_],B):-
    B == H.
check(A,B,[_|T],R):-
    check(A,B,T,R).
check(_,_,[],_).


%swap incase a set of letters isn't ordered, continues otherwise.
swap([X,Y|Rest],[Y,X|Rest],Order):-
    check(X,Y,Order,R),
    X == R.
swap([Z|Rest],[Z|Rest1],Order) :-
    swap(Rest,Rest1,Order).

When I run the code, it ends up crashing my swi-prolog, I'm assuming it's getting stuck in a loop or something, but haven't been able to figure out why or how.
Any advice or tips would be appreciated.

Upvotes: 3

Views: 888

Answers (1)

Shon
Shon

Reputation: 4098

Here's a solution to the stated problem, which does not, however, use a custom sorting algorithm. Instead, it uses the common pairs data-structure (using the (-)/2 operator to form a list of items Key-Value) and the keysort/2 for sorting. Edit: this answer has been reworked in accordance with @mat's tip in the comments, and to provide a more succinct explanation).

Solution:

item_with_rank(Ranking, Item, Rank-Item) :-
    nth0(Rank, Ranking, Item).

sort_by_ranking(Ranking, ToSort, Sorted) :-
    maplist(item_with_rank(Ranking), ToSort, Ranked),
    keysort(Ranked, RankedSorted),
    pairs_values(RankedSorted, Sorted).

Explanation:

We define a predicate item_with_rank(Ranking, Item, Rank-Item) that uses a list of arbitrarily ordered terms as a Ranking, and associates with the given Item a Rank which is equivalent to the 0-based index of the first term in Ranking that unifies with Item. We then define sort_by_ranking(Ranking, ToSort, Sorted). sort_by_ranking/3 uses maplist/3 to call item_with_rank/3, with the given Ranking, on each element of the list ToSort, obtaining a list of pairs, Ranked, assigning a rank to each item. We use keysort/2 to sort the Ranked so that they order of elements accords with the value of their "ranks" (keys) in RankedSorted. When we extract just the values from RankedSorted, we are left with the Sorted items, which is what we were after:

Example of usage:

?- sort_by_ranking([z,b,g,r,w], [r,z,z,w,g,g,r,z], S).
S = [z, z, z, g, g, r, r, w] ;
false.

Upvotes: 3

Related Questions