[Lisp] Construction d un arbre n-aire

Version imprimable

17/11/2006, 13h34
Treuze

[Lisp] Construction d un arbre n-aire

Bonjour,

Voilà, je travaille sous LISP, sur l'algorithme du sac à dos.

Pour optimiser le traitement, je pense utiliser un arbre n-aire mais j'ai beaucoup de mal à le générer par récursivité.

Par exemple, à partir de cette liste :
( x y z )

J'aimerais générer (l'ordre n'est pas important) :
( ( x y z ) ( x z ) ( y z ) ( z ) )

Je pense utiliser les fonctions ajout_en_tete, reste(liste), tete(liste),

Bien sûr cette fonction doit être extensible à n termes :
( a b c d )

donne la séquence :
( ( a b c d ) (a b d) (a c d ) ( c d ) ( b c d ) ( b d ) ( c d ) ( d ) )

Merci d'avance pour votre aide

Je n'ai pas bien compris le principe de construction
Le second ne serait pas
( ( a b c d ) (a b d) (a c d ) ( b c d ) (a d) ( b d ) ( c d ) ( d ) )
par hasard ?
Si c'est ça voilà un code en Scheme

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
;; pour chaque element de l on garde l'element et on ajoute en tête x
(define (sac-a-dos l)
  (let* ((ll (reverse l))
         (tete (list(list (car ll))))
         (reste (cdr ll)))
    (let foo1 ((x reste) (y tete))
      (cond ((null? x) y)
            (else (foo1 (cdr x) 
                        (let foo2 ((xx (car x)) (yy y))
                          (cond ((null? yy) yy)
                                (else (append (list (cons xx (car yy)) (car yy)) (foo2 xx (cdr yy))))))))))))
 
 
 
 
 
(sac-a-dos '(a b c d))
 
(sac-a-dos '(1 2 3))

Sortie

Citation:

((a b c d) (b c d) (a c d) (c d) (a b d) (b d) (a d) (d))
((1 2 3) (2 3) (1 3) (3))

18/11/2006, 17h14
Treuze

Merci ! Oui je me suis trompe ... mais je en comprends rien a ce que tu as fait:?

Le principe est de créer une liste avec le dernier élément d.
Puis pour chaque élément restant, je parcours la liste créée au tour précédent, pour chaque membre de cette liste, j'ajoute dans la nouvelle liste, ce membre et le membre augmenté de l'élément à ajouter en cours

ce qui donne pour la liste (a b c d)

init : ((d))
tour 1 : ((c d ) (d))
tour 2 : ((b c d) (c d) (b d) (d))
tour 3 : ((a b c d) (b c d) (a c d) (c d) (a b d) (b d) (a d) (d))

Ce qui donne dans le détail du code

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
;; pour chaque element de l on garde l'element et on ajoute en tête x
(define (sac-a-dos l)
  ;; j'ai besoin de la liste à l'envers
  ;; le let* permet en Scheme d'utiliser le résultat de "l'affectation précédent"
  ;; je mets des " car je ne connais pas le terme Scheme
  (let* ((ll (reverse l))
         ;; je crée le premier élément de l'init ((d))
         (tete (list(list (car ll))))
         ;; le reste est donc (c b a)
         (reste (cdr ll)))
    ;; création de la première fonction interne récursive
    ;; elle permet d'ajouter chaque élément à la liste
   ;; d'abord c puis b puis a
   ;; les arguments d'appel sont initialisés avec tete et reste
   ;; précédemment créés
    (let foo1 ((x reste) (y tete))
       ;; si tete est vide, on a fini, on renvoie la liste y
      (cond ((null? x) y)
            ;; sinon on rappelle foo1 avec comme premier argument
            ;; le reste de x (cdr x) et   comme second argument
            ;; la liste construite a partir de y et de (car x)
            (else (foo1 (cdr x) 
                        ;; appel de la fonction interne foo2
                        ;; qui construit récursivement la nouvelle liste en ajoutant
                        ;;  un membre de la liste et ce membre augmenté de xx
                        (let foo2 ((xx (car x)) (yy y))
                            ;; si la liste yy est vide c'est fini, on renvoie yy 
                          (cond ((null? yy) yy)
                            ;; sinon on construit la liste en ajoutant les deux nouveaux éléments crés à partir du premier élément de yy
                            ;; à la liste qui sera crée à partir des éléments restant de yy
                                (else (append (list (cons xx (car yy)) (car yy)) (foo2 xx (cdr yy))))))))))))

J'espère que tu as compris, ce n'est pas très simple à expliquer, tu peux essayer de faire ceci en utilisant des fonctions externes foo1 et foo2 au lieu d'être internes à sac-a-dos.

19/11/2006, 17h58
Treuze

Je me renseigne sur le Scheme pour comprendre ton programme , je suis sous emacs lisp...

J ai teste tt ca avecv drscheme , ca marche aussi pour une liste de 5 atom
Vraiment bravo ! Car ss savoir quelle logique je suivais, tu as trouve le bon algo, impressionnant !

Est ce que tu peux m explqiuer quelle methode/raisonnement tu as utilisé ?
19/11/2006, 19h22
Trap D

Ben, c'est en regardant les deux exemples que tu as fournis que j'en ai déduit ce que tu recherchais (je n'étais d'ailleurs pas trop sûr puisque tu avais fait une erreur).
Après il suffit d'avoir une idée comment le faire à la main, (en ce moment il y a beaucoup de questions de ce genre sur les listes), connaître un peu le principe de fonctionnement de Lisp / Scheme et ça roule.