[racket] From tree to lists : imperative or functionnal language ?
Hello
I am in difficulty with a recursive algorithm which build lists. Vn build a tree (lp) where all the suites of a list (l) where elements are either +2 either +3 from previous.
#lang scheme
(define (maxi l)
(- (length l) 1))
(define (Union l1 l2)
(if (empty? l2) l1
(list l1 l2)))
(define (U1n n l)
(if (>= (- (maxi l) n) 2)
(cons (list-ref l (+ n 2)) (Vn (+ n 2) l))
empty))
(define (U2n n l)
(if (>= (- (maxi l) n) 3)
(cons (list-ref l (+ n 3)) (Vn (+ n 3) l))
empty))
(define (Vn n l)
(if (>= (- (maxi l) n) 1)
(Union (U1n n l) (U2n n l))
empty))
(define l (list 'e_1 'e_2 'e_3 'e_4 'e_5 'e_6 'e_7 'e_8 'e_9 'e_10 'e_11))
(define lp (cons (first l) (Vn 0 l)))
; lp is (e_1 (e_3 (e_5 (e_7 (e_9 e_11) (e_10)) (e_8 (e_10) (e_11))) (e_6 (e_8 (e_10) (e_11)) (e_9 e_11))) (e_4 (e_6 (e_8 (e_10) (e_11)) (e_9 e_11)) (e_7 (e_9 e_11) (e_10))))
; I would like to unflat this tree and to have all the paths of the tree and to obtain :
; ((e_1 e_3 e_5 e_7 e_9 e_11) (e_1 e_3 e_5 e_7 e_10) (e_1 e_3 e_5 e_8 e_10) (e_1 e_3 e_5 e_8 e_11) (e_1 e_3 e_6 e_8 e_10) (e_1 e_3 e_6 e_8 e_11) (e_1 e_3 e_6 e_9 e_11) (e_1 e_4 e_6 e_8 e_10)
;(e_1 e_4 e_6 e_8 e_11) (e_1 e_4 e_6 e_9 e_11) (e_1 e_4 e_7 e_9 e_11) (e_1 e_4 e_7 e_10))
; I am trying, without any success (since 3 weeks), to obtain this list of lists, perhaps because i need a local list under building which change when a leave is reached
My poor and un-complete solution is
(define (1? l)
(equal? (length l) 1))
(define (simple-list? l)
(or (1? l)
(for/and ( [e l]) (not (list? e)))))
(define (flat r g d)
(cond
[(simple-list? g) (cons r g)]
[(simple-list? d) (cons r d)]
[else (list (cons r (flat (car g) (second g) (third g)))
(cons r (flat (car d) (second d) (third d))))]))
lp
(flat (car lp) (second lp) (third lp))
; which gives the un-complete solution ((e_1 (e_3 (e_5 e_7 e_9 e_11) (e_5 e_8 e_10)) (e_3 e_6 e_9 e_11)) (e_1 (e_4 e_6 e_9 e_11) (e_4 e_7 e_9 e_11)))
I could easily solve this problem in imperative language (C).
Do you think it could exist an elegant solution ?
I am doubting of a good solution in fonctionnal language as Racket.
Respectuously
*******************************************************
David Delfieu, tel : 02 40 90 50 45
EC à Polytech'Nantes - Département Génie Électrique
Site de Gavy, 44603 Saint Nazaire Cedex
Chercheur à L'IRCCyN
*******************************************************