scheme - 检查方案中的排列

Question

我需要在一个接受两个列表的方案中编写一个函数，如果一个列表是另一个列表的排列，则返回 true。
例如
(排列 '(3 4 7) '(7 3 4)) 将返回 #t
(排列 '(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

当且仅当

• 从 list2 中删除 list1 的元素生成空列表，和
• 从 list1 中删除 list2 的元素会生成空列表。

如果你有一个函数(让我们称它为“without”)从另一个列表中删除一个列表的所有元素，你可以这样写

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

剩下的就是先删除:

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

(在您的 Scheme 中，remove-first 可能已经作为 remove 可用。)