Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 14 sur 14
  1. #1
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut Couper une liste en deux

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

  2. #2
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

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

  3. #3
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    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.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  4. #4
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut 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.

  5. #5
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    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 ?
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  6. #6
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

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

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    Citation Envoyé par citron_666 Voir le message
    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.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  8. #8
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

    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.

  9. #9
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    Non, non, et non, il ne faut pas JAMAIS calculer la longueur de la chaine !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  10. #10
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

    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 ?

  11. #11
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    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.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  12. #12
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

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

  13. #13
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 574
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 574
    Points : 6 005
    Points
    6 005

    Par défaut

    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 :
    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] .
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  14. #14
    Invité de passage
    Inscrit en
    août 2012
    Messages
    15
    Détails du profil
    Informations forums :
    Inscription : août 2012
    Messages : 15
    Points : 2
    Points
    2

    Par défaut

    Citation Envoyé par Trap D Voir le message
    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.

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •