Schéma: utiliser backtracking pour trouver des permutations de phrases liste liste de caractères et liste de mots

Question

Donnée chars - une liste de caractères et words - et une liste de mots. Je souhaite trouver toutes les permutations possibles des phrases de la liste words donnée qui utilisent tous chars.

Par exemple:

chars = '(i l o v e t e l e v i s i o n)

words = '((i) (l o v e) (v i s i o n) (t e l e) (t e l e v i s i o n))

donc en cours d'exécution (find-permutations '(i l o v e t e l e v i s i o n) '((i) (l o v e) (v i s i o n) (t e l e) (t e l e v i s i o n))) donnera le résultat suivant:

(((i) (l o v e) (t e l e) (v i s i o n)) ((i) (l o v e) (t e l e v i s i o n)))

j'ai écrit le code suivant en utilisant le langage Scheme:

(define (substr sub str) 
    (cond ((null? sub) str) 
     ((null? str) #f) 
     ((eq? (car sub) (car str)) (substr (cdr sub) (cdr str))) 
     (else #f))) 

(define (find-permutations chars words) 

    (define (helper chars words1 result) 
    (cond ((null? chars) (reverse result)) 
      ((null? words1) null) 
      ((eq? chars #f) #f) 
      (else (let* (
         (x (substr (car words1) chars)) 
         (y (helper x words (cons (car words1) result))) 
         (w (helper chars (cdr words1) result)) 
         ) 
        (if x 
         (cons y w) 
         w) 
       ) 
       ) 

     ) 
    ) 

    (trace helper) 
    (helper chars words()) 
) 

mais je m'y suis trop entre parenthèses: ((((((i) (l o v e) (t e l e) (v i s i o n))) ((i) (l o v e) (t e l e v i s i o n)))))

je ne peux pas trouver pourquoi. Quelqu'un peut-il avoir une idée?

Answer 1

Vous devez utiliser append plutôt que cons

(define (substr? sub str) 
    (cond ((null? sub) str) 
     ((null? str) #f) 
     ((eq? (car sub) (car str)) (substr? (cdr sub) (cdr str))) 
     (else #f))) 

(define (find-permutations chars words) 
    (define (helper chars words1 result) 
    (cond ((null? chars) (reverse result)) 
      ((null? words1) #nil) 
      ((eq? chars #f) #f) 
      (else (let* ((chars-substr? (substr? 
          (car words1) chars)) 
         (head (helper chars-substr? words (cons (car words1) result))) 
         (tails (helper chars (cdr words1) result))) 
        (if chars-substr? 
         (append head tails) 
         tails))))) 

    (helper chars words '())) 

Lorsque vous cons ensemble deux listes que vous avez fait dans votre prédicat final (cons x y), vous créez une structure « imbriquée » en attribuant de nouveaux résultats à un chaîne plus profonde et plus profonde de car pointeurs.

Vous ne remarquerez peut-être pas cette différence subtile, car la convention impose d'omettre la structure «vraie» d'une liste d'expressions S, car la cellule car est le lieu où les données de liste associées sont généralement conservées.

Le schéma suivant montre la liste (1 . (2 . (3 . (4 .()), qui serait imprimée comme (1 2 3 4) en raison de cette convention.

Inversement, lorsque car détient une autre liste (plutôt que comme une valeur 1), il représente souvent une structure hiérarchique, qui est mis en forme avec plusieurs parenthèse englobante.