Генерация перестановок списка

Question

Я пишу функцию, которая принимает список и возвращает список перестановок аргумента.

Я знаю, как это сделать, используя функцию, которая удаляет элемент, а затем рекурсивно использует эту функцию для генерации всех перестановок.Теперь у меня возникла проблема, когда я хочу использовать следующую функцию:

(define (insert-everywhere item lst)
  (define (helper item L1 L2)
    (if (null? L2) (cons (append L1 (cons item '())) '())
        (cons (append L1 (cons item L2)) 
              (helper item (append L1 (cons (car L2) '())) (cdr L2)))))
  (helper item '() lst))

Эта функция будет вставлять элемент в каждое возможное место списка, как показано ниже:

(insert-everywhere 1 '(a b)) 

получит:

'((1 a b) (a 1 b) (a b 1))

Как бы я использовал эту функцию для получения всех перестановок списка?

Теперь у меня есть:

(define (permutations lst)
  (if (null? lst) 
      '()
      (insert-helper (car lst) (permutations (cdr lst)))))

(define (insert-helper item lst)
  (cond ((null? lst) '())
        (else (append (insert-everywhere item (car lst)) 
                    (insert-helper item (cdr lst))))))

, но я делаю (permutations '(1 2 3))просто возвращает пустой список '().

Answer 1

Сначала построим семейство связанных примеров :

(permutations      '()) = ???
(permutations     '(z)) = ???
(permutations   '(y z)) = ???
(permutations '(x y z)) = ???

Выясните, как каждый ответ связан с предыдущим. То есть как вы можете рассчитать каждый ответ с учетом предыдущего ответа (для хвоста списка) и нового элемента в начале списка?

Answer 2

Вот функция, которая генерирует все перестановки чисел с размером 'size', чтобы она состояла из элементов в списке 'items'

(define (generate-permutations items size)
  (if (zero? size)
      '(())
      (for/list ([tail (in-list (generate-permutations items (- size 1)))]
                 #:when #t
                 [i (in-list items)]
                 #:unless (member i tail))
        (cons i tail))))