Scheme: using backtracking to find sentence permutations given chars list and words list

Viewed 194

Given chars - a list of characters and words - and list of words. I wish to find all possible permutations of sentences from given words list that use all chars.

For example:

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 running (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))) will yield the following result:

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

I wrote the following code using Scheme language:

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

but i got too many brackets: ((((((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)))))

I can't find why. Can anyone have an idea?

1 Answers
Related