Implémentation d'un prédicat similaire à Transpose dans Prolog

Question

Je suis assez nouveau sur Prolog, en fait 4 jours après et je suis tombé sur un exercice qui déclare:

Étant donné une liste de N listes de taille N , chacune implémente un prédicat appelé reshape (X, Y) de sorte qu'il:

• Collecte les premiers éléments de toutes les listes dans une liste.
• Collecte les deuxièmes éléments de toutes les listes de listes dans une liste.
• ...
• Collecte les N éléments de toutes les listes dans une liste.
• Collecte toutes les listes mentionnées ci-dessus dans une nouvelle liste.

Un exemple serait:

• remodeler ([[1,2,3], [4,5,6], [7,8,9]], X )
• X = [[1,4,7], [2,5,8], [3,6,9]]

Voici donc ma mise en œuvre:

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

L'idée de base est donc que je commence par créer une liste de N listes vides, puis pour chaque liste, disons L de l'entrée, j'assigne / ajoute chaque élément de L à la liste correspondante.

Maintenant, j'apprécierais quelques commentaires car j'ai déjà dit que je suis nouveau sur Prolog et que je ne peux même pas dire quelle est la complexité temporelle de mon prédicat.

Quelle est la meilleure façon de le mettre en œuvre?

Quelle est la complexité temporelle de ma mise en œuvre? Cela ressemble à un temps polynomial mais je ne peux pas vraiment le dire.

Merci d'avance.

Answer 1

Vous pouvez coder un algorithme O (N) qui ne parcourt qu'une seule fois chaque élément:

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/3obtient la liste avec chaque premier élément de la liste des listes. Puis reshape/2construit toutes ces listes de manière récursive.

Cas de test:

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