Couper une liste en deux

**citron_666** · 10/08/2012, 15h01

Bonjour à tous,
Je souhaitais me faire une petite fonction qui coupe une liste en deux :

Code :

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

1
2
3
4
5
6
7
 
tronquer_liste(_, [], [], []).
tronquer_liste(0, Q, [], Q).
tronquer_liste(N, [T | Q], X, R) :-
	N1 is N - 1,
	tronquer_liste(N1, Q, X, R),
	X = [T | X].

On a un nombre qui correspond à la longueur de la liste qu'on veut récupérer, la liste sur laquelle on travaille et les deux derniers paramètres sont les deux bouts de listes résultats gauche et droite (j'espère être clair

). Hors lors de l’exécution voilà ce que j'obtiens :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
     26    3  Call: tronquer_liste(1,[pro101,pro102,pro103,pro104,pro105,pro106],_733,_734) ? 
     27    4  Call: _760 is 1-1 ? 
     27    4  Exit: 0 is 1-1 ? 
     28    4  Call: tronquer_liste(0,[pro102,pro103,pro104,pro105,pro106],_787,_788) ? 
     28    4  Exit: tronquer_liste(0,[pro102,pro103,pro104,pro105,pro106],[],[pro102,pro103,pro104,pro105,pro106]) ? 
     28    4  Redo: tronquer_liste(0,[pro102,pro103,pro104,pro105,pro106],[],[pro102,pro103,pro104,pro105,pro106]) ? 
     29    5  Call: _814 is 0-1 ? 
     29    5  Exit: -1 is 0-1 ? 
     30    5  Call: tronquer_liste(-1,[pro103,pro104,pro105,pro106],_841,_842) ? 
     31    6  Call: _868 is -1-1 ? 
     31    6  Exit: -2 is -1-1 ? 
     32    6  Call: tronquer_liste(-2,[pro104,pro105,pro106],_895,_896) ? 
     33    7  Call: _922 is -2-1 ? 
     33    7  Exit: -3 is -2-1 ? 
     34    7  Call: tronquer_liste(-3,[pro105,pro106],_949,_950) ? 
     35    8  Call: _976 is -3-1 ? 
     35    8  Exit: -4 is -3-1 ? 
     36    8  Call: tronquer_liste(-4,[pro106],_1003,_1004) ? 
     37    9  Call: _1030 is -4-1 ? 
     37    9  Exit: -5 is -4-1 ? 
     38    9  Call: tronquer_liste(-5,[],_1057,_1058) ? 
     38    9  Exit: tronquer_liste(-5,[],[],[]) ? 
     38    9  Redo: tronquer_liste(-5,[],[],[]) ? 
     38    9  Fail: tronquer_liste(-5,[],_1045,_1046) ? 
     36    8  Fail: tronquer_liste(-4,[pro106],_991,_992) ? 
     34    7  Fail: tronquer_liste(-3,[pro105,pro106],_937,_938) ? 
     32    6  Fail: tronquer_liste(-2,[pro104,pro105,pro106],_883,_884) ? 
     30    5  Fail: tronquer_liste(-1,[pro103,pro104,pro105,pro106],_829,_830) ? 
     28    4  Fail: tronquer_liste(0,[pro102,pro103,pro104,pro105,pro106],_775,_776) ? 
     26    3  Fail: tronquer_liste(1,[pro101,pro102,pro103,pro104,pro105,pro106],_721,_722) ?

J'ai essayé plein de manières différentes pour essayer de bloquer l'appel de la fonction lorsque N est 0 mais sans succès. Le problème avec le fail c'est qu'il bloque tous le reste de mon programme.

Edit : et encore une fois c'est sous GNU Prolog que ça se passe. ^^'

**citron_666** · 10/08/2012, 17h40

Bon je n'ai toujours pas trouvé la solution mais en changeant un peu le code :

Code :

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

1
2
3
4
5
6
7
8
9
 
tronquer_liste(_, [], [], []).
tronquer_liste(N, Q, [], Q) :-
	N =< 0.
tronquer_liste(N, [T | Q], X, R) :-
	N > 0,
	N1 is N - 1,
	tronquer_liste(N1, Q, X, R),
	X = [T | X].

J'obtiens un comportement différent :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
     10    4  Call: tronquer_liste(1,[2,78,23,7,9],_32,_33) ? 
     11    5  Call: 1=<0 ? 
     11    5  Fail: 1=<0 ? 
     11    5  Call: 1>0 ? 
     11    5  Exit: 1>0 ? 
     12    5  Call: _378 is 1-1 ? 
     12    5  Exit: 0 is 1-1 ? 
     13    5  Call: tronquer_liste(0,[78,23,7,9],_32,_33) ? 
     14    6  Call: 0=<0 ? 
     14    6  Exit: 0=<0 ? 
     13    5  Exit: tronquer_liste(0,[78,23,7,9],[],[78,23,7,9]) ? 
     13    5  Redo: tronquer_liste(0,[78,23,7,9],[],[78,23,7,9]) ? 
     14    6  Call: 0>0 ? 
     14    6  Fail: 0>0 ? 
     13    5  Fail: tronquer_liste(0,[78,23,7,9],_32,_33) ? 
     10    4  Fail: tronquer_liste(1,[2,78,23,7,9],_32,_33) ? 
      7    3  Fail: tronquer_liste(2,[5,2,78,23,7,9],_32,_33) ? 
      4    2  Fail: tronquer_liste(3,[4,5,2,78,23,7,9],_32,_33) ? 
      1    1  Fail: tronquer_liste(4,[1,4,5,2,78,23,7,9],_32,_33) ?

J'ai droit à un redo ...

**Trap D** · 10/08/2012, 18h00

Sans rien préjuger de ton code, X = [T |X] échoue toujours, X ne peut jamais être unifié avec [T | X], (en Prolog, il n'y a pas d'assignation, une variable garde toujours la même valeur dans une clause), conclusion ton code ne fonctionnera à mon avis jamais.

. Le problème avec le fail c'est qu'il bloque tous le reste de mon programme.

**citron_666** · 10/08/2012, 18h14

Le code qui marche :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
tronquer_liste(_, [], [], []).
tronquer_liste(N, Q, [], Q) :-
	N =< 0.
tronquer_liste(N, [T | Q], X, R) :-
	N > 0,
	N1 is N - 1,
	tronquer_liste(N1, Q, X1, R1),
	append([T], X1, L),
	X = L,
	R = R1.

Merci à celles et ceux qui se sont penchés sur mon problème.

**Trap D** · 10/08/2012, 22h08

Un petit défi algo : comment tronquer une liste en deux parties plus ou moins égales (à un près) sans en connaitre la longueur à l'avance ?

**citron_666** · 12/08/2012, 05h20

Déjà je ne savais pas qu'on pouvait rajouter des messages lorsqu'une discussion était marqué comme résolue, un petit défi qui a l'air simple et pourtant ... J'ai essayé de produire ce code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
tronquer_liste([], [], []).
tronquer_liste([T | Q], X, R) :-
	length(X, Len1),
	length(Q, Len2),
	Len1 < Len2,
	append(X, [T], L),
	tronquer_liste(Q, L, R1),
	X = L,
	R = R1.
tronquer_liste(Q, X, R) :-
	length(X, Len1),
	length(Q, Len2),
	Len1 >= Len2,
	R = Q.

Et pourtant à l’exécution j'obtiens les messages suivants :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
     16    4  Call: tronquer_liste([2,78,23,7,9],[1,4,5],_478) ? 
     17    5  Call: length([1,4,5],_502) ? 
     17    5  Exit: length([1,4,5],3) ? 
     18    5  Call: length([78,23,7,9],_527) ? 
     18    5  Exit: length([78,23,7,9],4) ? 
     19    5  Call: 3<4 ? 
     19    5  Exit: 3<4 ? 
     20    5  Call: append([1,4,5],[2],_580) ? 
     20    5  Exit: append([1,4,5],[2],[1,4,5,2]) ? 
     21    5  Call: tronquer_liste([78,23,7,9],[1,4,5,2],_612) ? 
     22    6  Call: length([1,4,5,2],_636) ? 
     22    6  Exit: length([1,4,5,2],4) ? 
     23    6  Call: length([23,7,9],_661) ? 
     23    6  Exit: length([23,7,9],3) ? 
     24    6  Call: 4<3 ? 
     24    6  Fail: 4<3 ? 
     22    6  Call: length([1,4,5,2],_636) ? 
     22    6  Exit: length([1,4,5,2],4) ? 
     23    6  Call: length([78,23,7,9],_661) ? 
     23    6  Exit: length([78,23,7,9],4) ? 
     24    6  Call: 4>=4 ? 
     24    6  Exit: 4>=4 ? 
     21    5  Exit: tronquer_liste([78,23,7,9],[1,4,5,2],[78,23,7,9]) ? 
     17    5  Call: length([1,4,5],_502) ? 
     17    5  Exit: length([1,4,5],3) ? 
     18    5  Call: length([2,78,23,7,9],_527) ? 
     18    5  Exit: length([2,78,23,7,9],5) ? 
     19    5  Call: 3>=5 ? 
     19    5  Fail: 3>=5 ? 
     16    4  Fail: tronquer_liste([2,78,23,7,9],[1,4,5],_466) ? 
     12    4  Call: length([1,4],_370) ? 
     12    4  Exit: length([1,4],2) ? 
     13    4  Call: length([5,2,78,23,7,9],_395) ? 
     13    4  Exit: length([5,2,78,23,7,9],6) ? 
     14    4  Call: 2>=6 ?

Je commence sérieusement à péter les plombs, ma liste de partie gauche a atteins la bonne taille et il ne devrait pas y avoir d'autre appel récursif à tronquer_liste (la partie en gras dans la trace d’exécution. Et pourtant le solveur arrive à me recalculer des tailles de listes qui n'existe pas.

Il va vraiment falloir m'expliquer ...

**Trap D** · 12/08/2012, 11h13

Envoyé par citron_666

Déjà je ne savais pas qu'on pouvait rajouter des messages lorsqu'une discussion était marqué comme résolue

On peut toujours continuer des discussions résolues si besoin est.
Là, c'est les vacances, et c'est un petit défi amusant dans la continuité de ton post.
Je n'ai pas le temps aujourd'hui de répondre à tes questions mais déjà, tu calcules des longueurs et donc ce n'est pas bon.

**citron_666** · 12/08/2012, 13h50

J'ai trouvé une solution plus élégante à mon premier problème sur Internet ...

Code :

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

1
2
3
 
split(L,0,[],L).
split([X|Xs],N,[X|Ys],Zs) :- N > 0, N1 is N - 1, split(Xs,N1,Ys,Zs).

Source
Du coup un peu dégouté d'avoir perdu mon temps sur cette question. Pour ton problème Trap D je dirais qu'il faut simplement calculer la longueur de la liste passé en paramètre avant d'utiliser la fonction split. Quelque chose dans ce style là :

Code :

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

1
2
3
4
 
split(L, X, Y) :- length(L, I), N is I // 2, split(L, N, X, Y).
split(L,0,[],L).
split([X|Xs],N,[X|Ys],Zs) :- N > 0, N1 is N - 1, split(Xs,N1,Ys,Zs).

Les deux codes marchent et font ce qu'on leur demande, sujet re-résolue by myself.

**Trap D** · 12/08/2012, 14h56

Non, non, et non, il ne faut pas JAMAIS calculer la longueur de la chaine !

**citron_666** · 12/08/2012, 19h07

J'imagine que tu as une solution plus élégante encore qui évite de calculer la longueur de la chaine. Mais je dois admettre que ta réaction m'interpelle, pourquoi ne faut il jamais calculer la longueur d'une liste ?

**Trap D** · 12/08/2012, 20h53

On s'est mal compris, pour le défi que je te propose, tu ne dois jamais calculer la longueur de la liste, c'est tout.
Pour d'autres algos, ça peut-être nécessaire.
Disons que le calcul de la longueur d'une liste peut-être très couteux (imagine une liste de 1 000 000 d'éléments, tu dois perdre du temps pour calculer la longueur), c'est pour ça que dans certains langage, le type String contient la longueur comme champs interne de la structure. Quand on peux éciter, on le fait.

**citron_666** · 12/08/2012, 22h26

Après de longues réflexions je dois admettre que je m'avoue vaincu.

**Trap D** · 12/08/2012, 23h21

Oh, c'est assez simple, il suffit d'y penser : on travaille sur deux listes, identiques, et à chaque fois qu'on enlève un élément à la première liste, on en enlève deux à la seconde.

Code :

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

1
2
3
4
5
6
7
8
9
couper(L, L1, L2) :-
	couper(L, L, L1, L2).
 
couper(L, [], [], L).
 
couper(L, [_], [], L).
 
couper([H | T], [_, _ | T1], [H | T2], L) :-
	couper(T, T1, T2, L).

exemple :

1 ?- couper([1,2,3,4,5,6], L1, L2).
L1 = [1,2,3],
L2 = [4,5,6] .

2 ?- couper([1,2,3,4,5,6,7], L1, L2).
L1 = [1,2,3],
L2 = [4,5,6,7] .

**citron_666** · 12/08/2012, 23h36

Envoyé par Trap D

Code :

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

1
2
3
4
5
6
7
8
9
couper(L, L1, L2) :-
	couper(L, L, L1, L2).

couper(L, [], [], L).

couper(L, [_], [], L).

couper([H | T], [_, _ | T1], [H | T2], L) :-
	couper(T, T1, T2, L).

Je dois admettre que la clause en gras je n'y aurais jamais pensé, bien joué Trap D.

Couper une liste en deux

Prolog

Discussions similaires

Partager

Partager