Implementacja predykatu podobnego do Transpose w Prologu

Question

Jestem całkiem nowy w Prologu, właściwie 4 dni po nim i natknąłem się na ćwiczenie, które stwierdza:

Biorąc pod uwagę listę N list o rozmiarze N, każda implementuje predykat o nazwie reshape (X, Y), tak aby:

• Zbiera pierwsze elementy wszystkich list w listę.
• Zbiera drugie elementy wszystkich list w postaci listy.
• ...
• Zbiera N elementów wszystkich list w listę.
• Zbiera wszystkie wymienione powyżej listy do nowej listy.

Przykładem może być:

• przekształcić ([[1,2,3], [4,5,6], [7,8,9]], X )
• X = [[1,4,7], [2,5,8], [3,6,9]]

Oto moja realizacja:

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

Więc podstawową ideą jest to, że zaczynam od stworzenia listy N pustych list, a następnie dla każdej listy powiedz L wejścia, które przypisuję / dodaję każdy element L do odpowiedniej listy.

Teraz byłbym wdzięczny za pewne dane wejściowe, ponieważ już powiedziałem, że jestem nowy w Prologu i nawet nie mogę powiedzieć, jaka jest złożoność czasowa mojego predykatu. Jedyne, co wiem na pewno, to to, że działa.

Czy jest lepszy sposób, w jaki mogę to wdrożyć?

Jaka jest złożoność czasowa mojego wdrożenia? Wydaje się, że jest to czas wielomianowy, ale naprawdę nie mogę powiedzieć.

Z góry dziękuję.

Answer 1

Możesz zakodować algorytm O (N), który przechodzi przez każdy element tylko raz:

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

reshape/3pobiera listę z każdym pierwszym elementem listy. Następnie reshape/2rekurencyjnie buduje wszystkie takie listy.

Przypadek testowy:

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