CODEWITHSUNDEEP
sortingprologswi-prolog
Martin Kunze
Martin Kunze

Reputation: 1055

Sort list of list in prolog?

In SWI-Prolog there is the predicate sort/2 to sort lists. Is there a good way to sort a list of list with fixed length by some index. I mean in example, if I have the following list of elements

Is there a function in SWI-Prolog to sort it by first or second index. By first index the result would be:

By second index:

Upvotes: 1

Views: 531

Answers (2)

repeat
repeat

Reputation: 18726

The efficient and portable way to get what you want goes like this:

  1. map each element X of the original list to a pair I-X, where I is the value to sort by.

  2. use keysort/2 on the resulting list; note that keysort/2 preserves duplicate items.

  3. at last, get rid of the values of I in the sorted list—we don't need them anymore.

The above directly translates to the predicate lists_sortedBySecondItem/2:

lists_sortedBySecondItem(Ess,Xss) :-
   maplist(list_pair,Ess,Pairs),             % (1)
   keysort(Pairs,Sorted),                    % (2)
   maplist(pair_second,Sorted,Xss).          % (3)

list_pair(Xs,I-Xs) :-
   nth(2,Xs,I).

pair_second(_-X,X).

Sample query using GNU Prolog 1.5.0:

| ?- lists_sortedBySecondItem([[1,2],[3,1],[2,5]], Xss).

Xss = [[3,1],[1,2],[2,5]]

yes

Upvotes: 2

brebs
brebs

Reputation: 4456

Can use https://www.swi-prolog.org/pldoc/doc_for?object=predsort/3 if removing duplicates is OK:

test(Nth1, S) :-
    L = [[1,2], [3,1], [2, 5], [1,2]],
    predsort(nth1_compare(Nth1), L, S).
    
nth1_compare(Nth1, Comp, L1, L2) :-
    nth1(Nth1, L1, V1),
    nth1(Nth1, L2, V2),
    compare(Comp, V1, V2).

Results:

?- test(1, S).
S = [[1,2],[2,5],[3,1]].

?- test(2, S).
S = [[3,1],[1,2],[2,5]].

Upvotes: 1

Related Questions