Couper une liste en deux

Version imprimable

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

Code:

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 :mrgreen:). Hors lors de l’exécution voilà ce que j'obtiens :

Code:

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. ^^'

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

Code:

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:

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 ... 8O

10/08/2012, 18h00
Trap D

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.

Citation:

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

Solution !

Le code qui marche :
Code:

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. :ccool:

10/08/2012, 22h08
Trap D

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 ?

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:

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:

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

12/08/2012, 11h13
Trap D

Citation:

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.
12/08/2012, 13h50
citron_666
J'ai trouvé une solution plus élégante à mon premier problème sur Internet ...
Code:

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:

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.
12/08/2012, 14h56
Trap D

Non, non, et non, il ne faut pas JAMAIS calculer la longueur de la chaine !
12/08/2012, 19h07
citron_666

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 ? :?
12/08/2012, 20h53
Trap D

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.
12/08/2012, 22h26
citron_666

Après de longues réflexions je dois admettre que je m'avoue vaincu.
12/08/2012, 23h21
Trap D
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:

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 :

Citation:

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

Citation:
Envoyé par Trap D
Code:

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. :ccool: