check for permutation in Scheme

Question

I need to write a function in a scheme that takes two lists and returns true if one list is a permutation of the other.
For example
(permutation '(3 4 7) '(7 3 4)) would return #t
(permutation '(3 4 7) '(c 3 4 5)) would return #f

This is the code I got so far but I'm stuck:

 (define (permutation list1 list2)
  (cond
    ((equal? list1 list2))
    ((not (list? list1)))
    ((memq (car list1) list2) (permutation (cdr list1) list2))
    (else #f)
    ))

Thank you

Answer 1

You have permutations if and only if

• removing the elements of list1 from list2 produces the empty list, and
• removing the elements of list2 from list1 produces the empty list.

If you had a function (let's call it "without") that removed all the elements of one list from another list, you could write

(define (permutation? xs ys)
  (and (empty? (without xs ys))
       (empty? (without ys xs))))

Assuming that you have a function remove-first that removes the first instance of an element from a list, you can define without using a fold:

(define (without xs ys)
    (foldl (lambda (x ls) (remove-first x ls)) ys xs))

All that remains is remove-first:

(define (remove-first x xs)
  (cond ((empty? xs) '())
        ((equal? x (first xs)) (rest xs))
        (else (cons (first xs) (remove-first x (rest xs))))))

(In your Scheme, remove-first may already be available as remove.)