Prolog中类似于Transpose的谓词的实现

Question

我对Prolog还很陌生，实际上已经4天了，我遇到了一个练习：

给定一个N大小为N+strong>的列表，每个列表都实现一个名为整形(X，Y(的谓词，使其：

• 将所有列表的第一个元素收集到一个列表中
• 将所有列表列表的第二个元素收集到一个列表中
• 将所有列表的N个元素收集到一个列表中
• 将上面提到的所有列表收集到一个新列表中

例如：

• 整形([[1,2,3]，[4,5,6]，[7,8,9]]，X(
• X=[[1,4,7]，[2,5,8]，[3,6,9]]

下面是我的实现：

% Insert at the end of a list
insert([],X,[X]).
insert([H|T1],X,[H|T2]) :- insert(T1,X,T2).

% Length of list
len([],L,L).
len([_|T],L,X) :- 
L1 is L + 1,
len(T,L1,X).
len(L,X) :- len(L,0,X).

% Create a list of N empty lists
init_list(L,0,L) :- !.
init_list(L,N,X) :-
N1 is N-1,
insert(L,[],Y),
init_list(Y,N1,X).
init_list(N,X) :- init_list([],N,X).

% Assign each element of a list to the corresponding list.
assign([],[],[]).
assign([H1|T1],[H2|T2],[Y|T3]) :- 
insert(H2,H1,Y),
assign(T1,T2,T3).

% Reshape :
reshape([],L,L).
reshape([H1|T1],X,Result):-
assign(H1,X,Y),
reshape(T1,Y,Result).    
reshape(Input,Result) :-
len(Input,N), 
init_list(N,X),
reshape(Input,X,Result).    

因此，基本的想法是，我首先创建一个由N个空列表组成的列表，然后对于每个列表，比如输入的L，我将L的每个元素分配/添加到相应的列表中。

现在，我很感激一些输入，因为我已经说过我是Prolog的新手，甚至不知道我的谓词的时间复杂性是多少。我唯一知道的是它是有效的。

但是，还有更好的方法可以实现它吗？

我的实现的时间复杂性是多少？它看起来像多项式时间，但我真的说不出来。

提前谢谢。

Answer 1

您可以编写一个只遍历每个元素一次的O(N(算法：

reshape([[]|Tail], []):-
maplist(=([]), Tail).
reshape(Input, [Result|RTail]):-
reshape(Input, LTail, Result),
reshape(LTail, RTail).

reshape([], [], []).
reshape([[Item|Tail]|LTail], [Tail|MTail], [Item|RTail]):-
reshape(LTail, MTail, RTail).

CCD_ 1获取具有列表列表的每个第一元素的列表。然后CCD_ 2递归地构建所有这样的列表。

测试用例：

?- reshape([[1,2,3],[4,5,6],[7,8,9]],X).
X = [[1, 4, 7], [2, 5, 8], [3, 6, 9]] ;
false.