Create a list of value pairs from 0 to n-1 in lexicographic order
I am making a program with the result 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 get 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 need the second answer (false), only the first. I want him to stop after he found the answer. Any ideas?
source to share
Keep in mind that there is a much easier way to get what you want. If in fact both X and Y must be integers, use between/3
to enumerate integers ("lexicographic" here is the same as the order of natural numbers: 0, 1, 2, ... This is the order in which it between/3
lists 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 use the usual Prolog way of representing a pair X-Y
(in canonical form:) -(X, Y)
instead of [X,Y]
(canonical form:) .(X, .(Y, []))
.
The nice thing about this program is that you can easily rewrite it to work with a different "alphabet" of your choice.
?- between(0, Upper, X).
semantically equivalent to:
x(0).
x(1).
% ...
x(Upper).
?- x(X).
For example, if we had an alphabet consisting 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 sentences foo/1
determines the order of your alphabet. The conjunction, foo(X), foo(Y)
together with the order X-Y
in the pair, determines the order of the pairs in the list. Try to write, for example, bagof(X-Y, ( foo(Y), foo(X) ), Ps)
to find out what the order of the pairs in Ps
.
?- use_module(library(lambda)).
In conjunction with meta-predicate init0/3
and
xproduct//2
("cross product") just 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 more general? How about other meanings 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? How about the order? Consider @ Boris's case 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
source to share