list - プロローグで行列を転置する方法

Question

[[1,2,3][4,5,6][6,7,8]]のようにリストを転置するにはどうすればよい[[1,4,6],[2,7,8],[3,6,9]]ですか?

説明するには: マトリックスを左に 90 度反転させたいと思います。どうやってやるの？

Answer 1

あなたの例が正しいかどうかはわかりませんが、私はその考えを理解しています。

SWI-PROLOG を使用している場合は、次のようにCLPFD モジュールを使用できます。

:- use_module(library(clpfd)).

transpose/2次のように、述語を使用できるようにします。

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

それ以外の場合 (SWI-PROLOG がない場合)、次の実装を使用できます (SWI の 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).

foldl および maplist ビルトインを使用する更新バージョンについては、 clpfd.pl を参照してください。

Answer 2

これは私が思いつくことができる最小のソリューションです。

コード

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).

テスト

:- transpose([[1,2,3],
              [4,5,6],
              [7,8,9]], R),
   print(R).

版画:

[[1,4,7],
 [2,5,8],
 [3,6,9]]

説明

それが機能する方法は、マトリックスの最初の列を抽出して転置するものtransposeを再帰的に呼び出すことです。transpose_1st_col例えば：

:- transpose_1st_col([[1,2,3],
                      [4,5,6],
                      [7,8,9]], Row, RestMatrix),
   print(Row),
   print(RestMatrix).

印刷します

[1,4,7]

と

[[2,3],
 [5,6],
 [8,9]]

これは入力行列が空になるまで繰り返され、その時点ですべての列が転置されます。次に、転置された列が転置された行列に結合されます。

Answer 3

これはより大きな答えの断片です:

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

Answer 4

より簡単なアプローチ:

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

効率的でもある

[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.

Answer 5

反復アプローチ:

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).

Answer 6

理解を深めるためのフルネームを使用した私のソリューション：

% 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).

「行」は、列または行にすることができます。

アイデアは、空の行列のリストに要素を追加することにあります。(たとえば、最初の行のすべての要素 = すべての列の最初の要素 => 最初の i-n 行目のすべての要素 = すべての列の i-n 番目の要素)

このセッションプロトコルが私に示すように、それは私のマシンで動作します:

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.