How to transpose a matrix in prolog
18,861
Solution 1
This is the smallest solution I could come up with.
Code
transpose([[]|_], []).
transpose(Matrix, [Row|Rows]) :- transpose_1st_col(Matrix, Row, RestMatrix),
transpose(RestMatrix, Rows).
transpose_1st_col([], [], []).
transpose_1st_col([[H|T]|Rows], [H|Hs], [T|Ts]) :- transpose_1st_col(Rows, Hs, Ts).
Test
:- transpose([[1,2,3],
[4,5,6],
[7,8,9]], R),
print(R).
Prints:
[[1,4,7],
[2,5,8],
[3,6,9]]
Explanation
The way it works is that transpose
will recursively call transpose_1st_col
which extracts and transposes the first column of the matrix. For example:
:- transpose_1st_col([[1,2,3],
[4,5,6],
[7,8,9]], Row, RestMatrix),
print(Row),
print(RestMatrix).
will print
[1,4,7]
and
[[2,3],
[5,6],
[8,9]]
This is repeated until the input matrix is empty, at which point all columns have been transposed. The transposed columns are then joined into the transposed matrix.
Solution 2
Here's a fragment of a larger answer:
% transposed(+A, ?B) iff matrix B is transposed matrix A
transposed(A, B) :- transposed(A, [], B).
transposed(M, X, X) :- empty(M), !.
transposed(M, A, X) :- columns(M, Hs, Ts), transposed(Ts, [Hs|A], X).
% empty(+A) iff A is empty list or a list of empty lists
empty([[]|A]) :- empty(A).
empty([]).
% columns(+M, ?Hs, ?Ts) iff Hs is the first column
% of matrix M and Ts is the rest of matrix M
columns([[Rh|Rt]|Rs], [Rh|Hs], [Rt|Ts]) :- columns(Rs, Hs, Ts).
columns([[]], [], []).
columns([], [], []).
Solution 3
Another simple approach:
transpose(M0, M) :-
nonvar(M0),
findall(L, maplist(nth1(_), M0, L), M).
?- transpose([[1,2,3],[4,5,6],[7,8,9]], M).
M = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]. `
Solution 4
simpler approach:
trans(M, [P|T]):- first(M, P, A), trans(A, T).
trans(Empty, []):- empty(Empty).
empty([[]|T]):- empty(T).
empty([[]]).
first([[P|A]|R], [P|Ps], [A|As]):- first(R, Ps, As).
first([], [], []).
efficient also
[debug] 36 ?- time(trans([[1,2,3],[4,5,6],[7,8,9]],A)).
% 21 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
A = [[1,4,7],[2,5,8],[3,6,9]] ;
% 12 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.
Author by
cody
Updated on July 23, 2022Comments
-
cody almost 2 years
How can I transpose a list like
[[1,2,3][4,5,6][6,7,8]]
to[[1,4,6],[2,7,8],[3,6,9]]
?To depict it: I'd like to flip the matrix 90 degree to the left. How can I do that?
-
cody over 13 yearsThanks :) perhaps this may be useful. First I prefer using the transpose/2 function, if I get it to work somehow...
-
false almost 10 yearsAny reason to put the simpler cases last?
-
Ricardo Zorio almost 10 yearsI can't order the results.