Create list of pair of values 0 to n-1 in lexicographical order

Question

I'm doing a program with Result is a pair of values [X,Y] between 0 and N-1 in lexicographic order

I have this right now:

pairs(N,R) :-
   pairsHelp(N,R,0,0).

pairsHelp(N,[],N,N) :- !.
pairsHelp(N,[],N,0) :- !.
pairsHelp(N,[[X,Y]|List],X,Y) :-
    Y is N-1,
    X < N,
    X1 is X + 1,
    pairsHelp(N,List,X1,0).
pairsHelp(N,[[X,Y]|List],X,Y) :-
    Y < N,
    Y1 is Y + 1,
    pairsHelp(N,List,X,Y1).

I'm getting what I want the first iteration but Prolog keeps going and then gives me a second answer.

?-pairs(2,R).
R = [[0,0],[0,1],[1,0],[1,1]] ;
false.

I don't want the second answer (false), just the first. I want it to stop after it finds the answer. Any ideas?

See [this question](http://stackoverflow.com/q/31164078/772868) for the `false`. It's completely harmless. — false, Jul 20 '15 at 06:23

score 4 · Accepted Answer · 2015-07-20T12:16:14.090

Keep in mind that there is a much easier way to get what you are after. If indeed both X and Y are supposed to be integers, use between/3 to enumerate integers ("lexicographical" here is the same as the order of natural numbers: 0, 1, 2, .... This is the order in which between/3 will enumerate possible solutions if the third argument is a variable):

pairs(N, R) :-
    succ(N0, N),
    bagof(P, pair(N0, P), R).

pair(N0, X-Y) :-
    between(0, N0, X),
    between(0, N0, Y).

And then:

?- pairs(2, R).
R = [0-0, 0-1, 1-0, 1-1].

?- pairs(3, R).
R = [0-0, 0-1, 0-2, 1-0, 1-1, 1-2, 2-0, 2-1, ... - ...].

I am using the conventional Prolog way of representing a pair, X-Y (in canonical form: -(X, Y)) instead of [X,Y] (canonical form: .(X, .(Y, []))).

The good thing about this program is that you can easily re-write it to work with another "alphabet" of your choosing.

?- between(0, Upper, X).

is semantically equivalent to:

x(0).
x(1).
% ...
x(Upper).

?- x(X).

For example, if we had an alphabet that consists of b, a, and c (in that order!):

foo(b).
foo(a).
foo(c).

foo_pairs(Ps) :-
    bagof(X-Y, ( foo(X), foo(Y) ), Ps).

and then:

?- foo_pairs(R).
R = [b-b, b-a, b-c, a-b, a-a, a-c, c-b, c-a, ... - ...].

The order of the clauses of foo/1 defines the order of your alphabet. The conjunction foo(X), foo(Y) together with the order of X-Y in the pair defines the order of pairs in the list. Try writing for example bagof(X-Y, ( foo(Y), foo(X) ), Ps) to see what will be the order of pairs in Ps.

score 2 · Answer 2 · edited May 23 '17 at 11:50

Use dcg in combination with lambda!

?- use_module(library(lambda)).

In combination with meta-predicate init0/3 and xproduct//2 ("cross product") simply write:

?- init0(=,3,Xs), phrase(xproduct(\X^Y^phrase([X-Y]),Xs),Pss).
Xs = [0,1,2], Pss = [0-0,0-1,0-2,1-0,1-1,1-2,2-0,2-1,2-2].

How about something a little more general? What about other values of N?

?- init0(=,N,Xs), phrase(xproduct(\X^Y^phrase([X-Y]),Xs),Pss).
  N = 0, Xs = [],          Pss = []
; N = 1, Xs = [0],         Pss = [0-0]
; N = 2, Xs = [0,1],       Pss = [0-0,0-1,
                                  1-0,1-1]
; N = 3, Xs = [0,1,2],     Pss = [0-0,0-1,0-2,
                                  1-0,1-1,1-2,
                                  2-0,2-1,2-2]
; N = 4, Xs = [0,1,2,3],   Pss = [0-0,0-1,0-2,0-3,
                                  1-0,1-1,1-2,1-3,
                                  2-0,2-1,2-2,2-3,
                                  3-0,3-1,3-2,3-3] 
; N = 5, Xs = [0,1,2,3,4], Pss = [0-0,0-1,0-2,0-3,0-4,
                                  1-0,1-1,1-2,1-3,1-4,
                                  2-0,2-1,2-2,2-3,2-4,
                                  3-0,3-1,3-2,3-3,3-4,
                                  4-0,4-1,4-2,4-3,4-4]
...

Does it work for other terms, too? What about order? Consider a case @Boris used in his answer:

?- phrase(xproduct(\X^Y^phrase([X-Y]),[b,a,c]),Pss).
Pss = [b-b,b-a,b-c,a-b,a-a,a-c,c-b,c-a,c-c].  % succeeds deterministically

Create list of pair of values 0 to n-1 in lexicographical order

2 Answers2