Discussion :

[West01]

Bonjour,

Je voudrais savoir comment fais-ton pour regrouper une liste en une liste de listes.

Ainsi, je voudrais regrouper les mêmes éléments qui sont identiques d'une liste triée auparavant.


Exemples:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
?- regrouper([1,1,2,2,3,4], L).
  L = [[1,1], [2,2], [3], [4]];
  NO
 
?- regrouper([1,2,3,4], L).
  L = [[1], [2], [3], [4]];
  NO

Pour ce qui est du tri, c'est correct. Mais c'est de regrouper qui me cause une problème.

Ça fait un bon 8 heures que je suis la-dessus

Voici un bout de code que j'ai fait, mais il y a des bogues par ci et par là...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 
  regrouper([], []).
  regrouper([X|L], LR):- rgp2(X, L, LR).
  rgp2(X, [], [X]).
  rgp2(X, [Y | LE], [ [X | R1 ] | _]) :- X = Y, !, rgp2(Y, LE, R1).
  rgp2(X, [Y | LE], [ X | R2]) :- \+ X = Y, !, rgp2(Y, LE, R2).

Merci d'avance pour tout aide.

[Trap D]

A mon avis tu devrais utiliser une liste d'accumulation pour effectuer le travail.
Cette liste te permettrait de comparer le premier élément de la liste à étudier avec le premier élément de la première liste de la liste d'accumulation. j'espère que je suis clair
Il faut aussi initialiser cette liste.

[West01]

Merci Trap D pour ta réponse.

Mais ça reste flou le concept de liste d'accumulation...

D'autres suggestions...

[Trap D]

Le principe de la liste d'accumulation c'est ça : imagine la fonction reverse qui inverse une liste, on peut l'écrire de cette manière avec 3 arguments
my_reverse(LI, LC, LF).
LI liste à inverser
LC liste en construction, (c'est la liste d'accumulation)
LF liste finale
On aura comme clauses :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
my_reverse([], L, L).
% On n'a plus rien à inverser, la liste finale est unifiée avec la liste en construction
 
my_reverse([H |T], LC, LF) :-
  my_reverse(T, [H | LC], LF).
% Le premier élément de la liste à inverser 
% est mis en tête de la liste en construction
% et on continue avec le reste de la liste à inverser

Pour ton problème tu peux démarrer comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
regrouper([H| T], L) :-
  regrouper(T, [[H]], L).

Le deuxième argument de regrouper/3 est initialisé avec le premier argument de la liste à travailler. L est la liste finale.

[polochonad]

bjr,
voici une autre solution...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
% pack(L1,L2) :- (list,list) (+,?)
 
pack([],[]).
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).
 
 
transfer(X,[],[],[X]).
transfer(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y.
transfer(X,[X|Xs],Ys,[X|Zs]) :- transfer(X,Xs,Ys,Zs).

[polochonad]

c'est en sicstus prolog, je pense que le " \=" est le meme en swi-prolog, c'est la seule modification a faire si ce n'est pas le cas

[Trap D]

Je préfère plutôt cette version :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
% pack(L1,L2) :- (list,list) (+,?)
 
pack([],[]).
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).
 
transfer(X,[],[],[X]).
transfer(X,[X|Xs],Ys,[X|Zs]) :- !, transfer(X,Xs,Ys,Zs).
transfer(X,[Y|Ys],[Y|Ys],[X]).

[polochonad]

pas mal Trap D, j'avais pas pensé
on peut dire alors que c'est

[Trap D]

On divise presque le nombre d'inférences par 3

30 ?-
% d:/Developpements/Prolog/DVP/dictionnaire.pl compiled 0.00 sec, 0 bytes
30 ?- time(pack([1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,6,6,7,7,7,8,8,8], L)).
% 90 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips)

L = [[1, 1, 1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3|...], [4, 4, 4, 4, 4], [6, 6], [7, 7, 7], [8, 8|...]] ;

No
31 ?-
% d:/Developpements/Prolog/DVP/dictionnaire.pl compiled 0.00 sec, -16 bytes
31 ?- time(pack([1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,6,6,7,7,7,8,8,8], L)).
% 38 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips)

L = [[1, 1, 1, 1], [2, 2, 2, 2, 2, 2], [3, 3, 3, 3, 3, 3|...], [4, 4, 4, 4, 4], [6, 6], [7, 7, 7], [8, 8|...]] ;

No

En 30 c'est ta version de transfer en 31 la mienne.

Pour le c'est au PO de décider

[polochonad]

pourra tu m'expliquer le pourquoi?! est-ce dans l'appel de l'algo d'unification au niveau de "\=", ou bien du "cut" qui supprime plein de branche ds l'arbre de recherche...?! une explication de ton analyse empirique sera la bienvenue

[Trap D]

Sans en être tout à fait certain, j'aurais tendance à penser que quelques soient les valeurs de X et Y, on entre dans la clause

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

transfer1(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y.

donc on effectue obligatoirement ce test, ce qui est rendu inutile en inversant les clauses.
Je pense pas que le cut y soit pour quelque chose.

[polochonad]

oui tu a tout a fait raison, c'est bien logique qu'il teste a chaque fois, tu pourra le visualisé en faisant la trace du programme...
pour le cut, si dans la trace du programme ya des backtrack, alors soi sur que le cut optimise bcp en enlevant les branches de l'arbre

[Trap D]

Oui, mais ici le cut est destiné à empécher la dernière clause de transfer d'être exécutée.
Par rapport à ton code, il me fait l'effet d'être comme ton test \X = Y