Schema: Verwenden von Backtracking zu Satzvertauschungen gegeben gegeben Chars-Liste und Wörterliste

Question

Gegeben chars - eine Liste von Zeichen und words - und Liste der Wörter. Ich möchte alle möglichen Permutationen von Sätzen von gegebenen words Liste finden, die alle chars verwenden.

Zum Beispiel:

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

So (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))) ausgeführt wird folgendes Ergebnis ergeben:

(((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)))

ich mit dem folgenden Code Schema Sprache geschrieben:

(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()) 
) 

, aber ich habe zu viele Klammern: ((((((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)))))

Ich kann nicht finden, warum. Kann jemand eine Idee haben?

Answer 1

sollten Sie append verwenden, anstatt 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 '())) 

Wenn Sie cons zusammen zwei Listen, wie Sie in Ihrem letzten Prädikat tat (cons x y), Sie werden durch die Zuordnung Ihrer neuen Ergebnisse eine eine „verschachtelte“ Struktur zu schaffen tiefere und tiefere Kette von car Zeigern.

Sie werden diesen subtilen Unterschied möglicherweise nicht bemerken, da die Konvention es vorschreibt, die 'wahre' Struktur einer S-Ausdruck-Liste wegzulassen, weil die car Zelle die zugehörigen Listen-Daten enthält.

Das folgende Diagramm zeigt die Liste (1 . (2 . (3 . (4 .()), die aufgrund dieser Konvention als (1 2 3 4) gedruckt werden würde.

Umgekehrt, wenn car weitere Liste (eher als einen Wert wie 1) hält, stellt sie häufig eine hierarchische Struktur, die mit mehreren einschließenden Klammern formatiert ist.