CODEWITHSUNDEEP
matrixprolog
john_ny
john_ny

Reputation: 173

Triangular matrices in Prolog

I am trying to write a program that identifies upper triangular matrices. I am quite new to Prolog and i would like your assistance on this.

Considering a matrix as a list of lists, where each list is a matrix row, how can I do it with basic predicates only, such as append, reverse, prefix, sublists, length etc ? (will not probably use all these predicates but just to give you an idea)

My attempts failed, mainly because I cannot access the elements of each list/row properly.

Upvotes: 0

Views: 220

Answers (1)

slago
slago

Reputation: 5519

In SWI-Prolog, you can use the predicate nth0/3 to access elements of a list (indexing from 0).

For example, to access the element in the third column (J = 2) of the second row (I = 1) of matrix M, you can ask:

?- M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]], nth0(1, M, R), nth0(2, R, C).
M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
R = [0, 40, 50],
C = 50.

So, you can define the following predicate to access elements of a matrix:

element(I, J, M, C) :-
    nth0(I, M, R),
    nth0(J, R, C).

matrix([[10, 20, 30],
        [ 0, 40, 50],
        [ 0,  0, 60]]).

Example:

?- matrix(M), element(I, J, M, X).
M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = J, J = 0,
X = 10 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = 0,
J = 1,
X = 20 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = 0,
J = 2,
X = 30 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = 1,
J = X, X = 0 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = J, J = 1,
X = 40 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = 1,
J = 2,
X = 50 
...

Now that you know how to access the elements, I think you can find a way to solve your problem.

Hint: Use the predicate forall/2 to define this rule in Prolog:

A matrix M is upper triangular if 
   For every element Xij of M such that j<i, 
   we have Xij = 0.

EDIT Another possible solution, using append/3 and length/2, is:

elem(I, J, M, X) :-
    append(Prefix1, [Row|_], M),
    append(Prefix2, [X|_], Row),
    length(Prefix1, I),
    length(Prefix2, J).

Examples:

?- matrix(M), elem(1, 2, M, X).
M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
X = 50 ;
false.

?- matrix(M), elem(I, J, M, X).
M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = J, J = 0,
X = 10 ;

M = [[10, 20, 30], [0, 40, 50], [0, 0, 60]],
I = 0,
J = 1,
X = 20 
...
false;

Upvotes: 1

Related Questions