проверка на перестановку в схеме

Question

Мне нужно написать функцию в схеме, которая принимает два списка и возвращает true, если один список является перестановкой другого.Например(permutation '(3 4 7) '(7 3 4)) вернул бы #t(permutation '(3 4 7) '(c 3 4 5)) вернется # f

Это код, который я получил до сих пор, но я застрял:

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

Спасибо

Answer 1

У вас есть перестановки, если и только если

• удаление элементов list1 из list2 приводит к пустому списку, и
• удалениеэлементы list2 из list1 создают пустой список.

Если бы у вас была функция (назовем ее «без»), которая удалила все элементы одного списка из другого списка, вы могли быwrite

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

Предполагая, что у вас есть функция remove-first, которая удаляет первый экземпляр элемента из списка, вы можете определить without, используя сгиб:

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

Осталось только 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))))))

(В вашей схеме remove-first может быть уже доступно как remove.)