How to transpose a matrix in prolog

Question

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?

Fretwell

Answer 1

Not sure your example is correct, but I get the idea.

If using SWI-PROLOG, you can use the CLPFD module, like so:

:- use_module(library(clpfd)).

Allowing you to use the transpose/2 predicate, like this:

1 ?- transpose([[1,2,3],[4,5,6],[6,7,8]], X).
X = [[1, 4, 6], [2, 5, 7], [3, 6, 8]].

Otherwise (if no SWI-PROLOG), you could simply use this implementation (which happened to be an old one in SWI's clpfd):

transpose([], []).
transpose([F|Fs], Ts) :-
    transpose(F, [F|Fs], Ts).

transpose([], _, []).
transpose([_|Rs], Ms, [Ts|Tss]) :-
        lists_firsts_rests(Ms, Ts, Ms1),
        transpose(Rs, Ms1, Tss).

lists_firsts_rests([], [], []).
lists_firsts_rests([[F|Os]|Rest], [F|Fs], [Os|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).

For an updated version which uses foldl and maplist built-ins, see clpfd.pl.

Libreville

Thanks! I'm using SWI Prolog and tried your first solution. But when typing "use_module(library(clpfd))." I get the following error: "ERROR: source_sink `library(clpfd)' does not exist" Do you know how to solve that? – Fretwell

I'm guessing that either you don't actually have the clpfd library, or your installation of SWI-PL is busted. clpfd.pl should reside in directory library/clp (under the SWI-PL home directory). If it is there, then perhaps SWI-PL just couldn't find it; in this case, perhaps your pl executable has a different name to the ___.rc configuration file, also in the SWI-PL root directory (they must be identical). Otherwise, simply just use the definition I've posted which is the implementation of clpfd's transpose/2 anyway. – Libreville

Ok. The library was missing and I copied it into library/clp. But it still doesn't work. I've got a file named "plwin.rc" in the pl-root dir, and a bin-folder with the executables. Moving the .rc into the bin folder doesn't solve it.. so do I have to modify it? – Fretwell

If the library was initially missing, your copy of SWI-PL mightn't have been configured to check for libraries in that location, so simply copying files around probably won't achieve much (you may have a configuration problem instead, which I'm not sure how to solve without seeing your system). Try upgrading to the latest version: swi-prolog.org/download/stable – Libreville

@sharky: nice answer, +1! there is new code in library(clpfd) that manages to do this more elegantly now. The link to the source code has also changed. I hope you can update the answer accordingly. – Alkylation

@Alkylation thank you. I've provided a link to the updated implementation in clpfd, but I've left the old implementation in my answer because I like it better (it doesn't use built-ins which other implementations of Prolog mightn't have). – Libreville

Answer 2

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.

Infare

Why do you have transpose([[]|_], []). instead of transpose([], []).? – Surmise

Answer 3

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([], [], []).

Emmalynn

Thanks :) perhaps this may be useful. First I prefer using the transpose/2 function, if I get it to work somehow... – Fretwell

Answer 4

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]]. `

Bandmaster

Answer 5

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.

Athematic

Any reason to put the simpler cases last? – Anderson

I can't order the results. – Athematic

Answer 6

An iterative approach:

trans([H|R],[H1|R1]):-trans2([H|R],[H|R],[],[H1|R1],0),!.
trans2([A|_],_,_,[],N):-length(A,N).
trans2(M,[],H1,[H1|R1],N):-N1 is N+1, trans2(M,M,[],R1,N1).
trans2(M,[H|R],L,[H1|R1],N):-nth0(N,H,X),
   append(L,[X],L1),trans2(M,R,L1,[H1|R1],N).

Benison

Answer 7

My solution with full names for a better understanding:

% emptyMatrix(Line, EmptyMatrix)
emptyMatrix([],[]).
emptyMatrix([_|T1],[[]|T2]):-emptyMatrix(T1,T2).
% only length of parameter 'Line' is interesting. It ignores its content.    

% appendElement(Element, InputList, OutputList)
appendElement(E,[],[E]).
appendElement(E,[H|T],[H|L]):-appendElement(E,T,L).

% appendTransposed(NestedList, InputMatrix, OutputMatrix)
appendTransposed([],[],[]).
appendTransposed([X|T1],[],[[X]|T3]):-appendTransposed(T1,[],T3).
appendTransposed([X|T1],[R|T2],[C|T3]):-appendElement(X,R,C),appendTransposed(T1,T2,T3).

% transposeMatrix(InputMatrix, TransposedMatrix)
transposeMatrix([L|M],T):-emptyMatrix(L,A),transpose([L|M],T,A).
transpose([],T,T).
transpose([L|M],T,A):-appendTransposed(L,A,B),transpose(M,T,B).

A 'line' can be a col or a row.

The idea lies in appending the elements into the lists of an empty matrix. (e.g. all elements of the first row = the first elements of all cols => all elements of the first i-nth row = the i-nth elements of all cols)

It works on my machine as this session protocol shows to me:

5 ?- transposeMatrix([[1,2],[3,4]],T).
T = [[1, 3], [2, 4]] ;
false.

6 ?- transposeMatrix([[1],[2]],T).
T = [[1, 2]] ;
false.

7 ?- transposeMatrix([[1,2,3],[4,5,6]],T).
T = [[1, 4], [2, 5], [3, 6]] ;
false.

8 ?- transposeMatrix([[1]],T).
T = [[1]] ;
false.

Alex

Answer 8

Another approach:

delete_one_list([], []).
delete_one_list([[_|L]|LLs], [L|Ls]) :-
  delete_one_list(LLs, Ls).

transpose_helper([], []).
transpose_helper([[X|_]|Xs], [X|Ys]) :-
  transpose_helper(Xs, Ys).

transpose([[]|_], []).
transpose(List, [L|Ls]) :-
  transpose_helper(List, L),
  delete_one_list(List, NewList),
  transpose(NewList, Ls).

Slovakia