How to sort output in Prolog?

Question

I have the following predicate:

soln(L,M,O,R,S,V) :-
    permutation([L,M,O,R,S,V],[1,2,3,4,5,6]),
    R=\=S+1,
    R=\=S-1,
    M=:=L+1,
    O>M,
    O<S.

When I call it from the REPL, it prints out correct answers:

?- soln(L,M,O,R,S,V).
L = 1,
M = 2,
O = 3,
R = 4,
S = 6,
V = 5 ;
L = 1,
M = 2,
O = 3,
R = 6,
S = 4,
V = 5 .

However, more useful to me would be output where the variables are sorted according to their value; to use the previous example, something like [L,M,O,R,V,S], [L,M,O,S,V,R], ... would be ideal.

I would like to be able to do this both in the REPL and in a standalone script.

Answer 1

If you want to sort the names according according to their values, you have to keep track of an association between variables and their names.

This is because the variable names you see in the source code are not accessible within the Prolog program, so you have to keep track of the names in a way that is accessible within Prolog.

One way to do it is to keep track of a list of pairs of the form Variable-Name. This way, when the variable is bound to a value, you still know its intended name.

Therefore, I suggest the following slight rewrite:

:- use_module(library(clpfd)).

solution(Pairs) :-
        Vs = [L,M,O,R,S,_V],
        Names = [l,m,o,r,s,v],
        pairs_keys_values(Pairs, Vs, Names),
        R #\= S+1,
        R #\= S-1,
        M #= L+1,
        O #> M,
        O #< S,
        Vs ins 1..6.

Note that I am now using the atoms l, m, o etc. to denote the names of the variables, and I now reason about pairs. Further, I have taken the liberty to express this all with constraints, so we benefit from constraint propagation instead of having to try each permutation. Using constraints, the Prolog engine can prune a significant portion of the search space without even trying it. I am using _V to denote the variable V, because this variable is not mentioned anywhere else, and using V therefore would result in a singleton warning.

We can already try it out:

?- solution(Pairs),
   pairs_keys_values(Pairs, Vs, Names),
   label(Vs).
Pairs = [1-l, 2-m, 3-o, 1-r, 4-s, 1-v],
Vs = [1, 2, 3, 1, 4, 1],
Names = [l, m, o, r, s, v] ;
Pairs = [1-l, 2-m, 3-o, 1-r, 4-s, 2-v],
Vs = [1, 2, 3, 1, 4, 2],
Names = [l, m, o, r, s, v] ;
Pairs = [1-l, 2-m, 3-o, 1-r, 4-s, 3-v],
Vs = [1, 2, 3, 1, 4, 3],
Names = [l, m, o, r, s, v] ;
etc.

Now, to sort the names according to the values of these variables, use the ISO predicate keysort/2, which sorts pairs according to their keys, i.e., their first component:

?- solution(Pairs0),
   pairs_keys_values(Pairs0, Vs0, Names0),
   label(Vs0),
   keysort(Pairs0, Pairs),
   pairs_values(Pairs, Names).
Pairs0 = [1-l, 2-m, 3-o, 1-r, 4-s, 1-v],
Vs0 = [1, 2, 3, 1, 4, 1],
Names0 = [l, m, o, r, s, v],
Pairs = [1-l, 1-r, 1-v, 2-m, 3-o, 4-s],
Names = [l, r, v, m, o, s] ;
Pairs0 = [1-l, 2-m, 3-o, 1-r, 4-s, 2-v],
Vs0 = [1, 2, 3, 1, 4, 2],
Names0 = [l, m, o, r, s, v],
Pairs = [1-l, 1-r, 2-m, 2-v, 3-o, 4-s],
Names = [l, r, m, v, o, s] ;
Pairs0 = [1-l, 2-m, 3-o, 1-r, 4-s, 3-v],
Vs0 = [1, 2, 3, 1, 4, 3],
Names0 = [l, m, o, r, s, v],
Pairs = [1-l, 1-r, 2-m, 3-o, 3-v, 4-s],
Names = [l, r, m, o, v, s] ;
Pairs0 = [1-l, 2-m, 3-o, 1-r, 4-s, 4-v],
Vs0 = [1, 2, 3, 1, 4, 4],
Names0 = [l, m, o, r, s, v],
Pairs = [1-l, 1-r, 2-m, 3-o, 4-s, 4-v],
Names = [l, r, m, o, s, v] ;
etc.