Используйте промежуточный язык в racket для поиска перестановок списка [duplicate]

Выберем это отдельно, исходя изнутри. Исправьте lst и примените внутреннее выражение к одному из его элементов.

> (define lst '(1 2 3))
> (define i 1)
> (permute (remove i lst))
((2 3) (3 2))

Выглядит хорошо: внутреннее выражение удаляет элемент и генерирует перестановки остальной части списка, рекурсивно. Теперь map lambda над этими перестановками:

> (map (lambda (j) (cons i j)) (permute (remove i lst)))
((1 2 3) (1 3 2))

Таким образом, внутренний map создает все перестановки, которые начинаются с некоторого i, который мы установили здесь 1.

Внешняя map гарантирует, что все перестановки генерируются, рассматривая все элементы из lst как первый элемент.

> (map (lambda (i) (map (lambda (j) (cons i j))
>                       (permute (remove i lst))))
>      lst)
(((1 2 3) (1 3 2)) ((2 1 3) (2 3 1)) ((3 1 2) (3 2 1)))

Но это создает списки со слишком большим количеством вложенности. Применение append выравнивает список списков

> (append '(1 2) '(3 4) '(5 6))
(1 2 3 4 5 6)
> (apply append '((1 2) (3 4) (5 6)))
(1 2 3 4 5 6)

, поэтому мы получаем плоский список перестановок.

Мне всегда было легче понять алгоритм на более высоком уровне, прежде чем погрузиться в реализацию и попытаться понять, что там происходит. Итак, возникает вопрос: каковы перестановки списка и как вы их найдете?

Перестановки одного списка элементов, по-видимому, являются только самим списком.

Перестановки (a b) являются множеством [(a b) (b a)].

Перестановки (a b c) - это множество

[(a b c) (a c b) (b c a) (b a c) (c a b) (c b a)]

. В общем случае существуют n! перестановки списка длины n - у нас есть n вариантов для первого элемента, и как только мы выбрали это, (n-1) выбор для второго элемента (n-2) для третьего элемента и так далее. Это уменьшение степеней свободы по мере того, как мы фиксируем все больше и больше первых элементов списка, очень наводящий на размышления: возможно, мы можем представить нахождение перестановок списка длины n в терминах перестановок списка длины (n - 1) и так далее, пока мы не достигнем перестановок одноэлементного списка.

Оказывается, что перестановки списка точно представляют собой набор [элемент, добавленный к перестановкам списка \ element, для каждого элемента в списке].

Глядя на случай (a b c), подтверждает, что это правда - мы имеем a, предшествующие (b c) и (c b), которые являются перестановками (b c), b, предшествующими (a c) и (c a) и т. д. Эта операция добавления элемента в подсписку может быть определена как

(define (prepend j)
  (cons element j))

, и тогда выполнение этой операции для всех перестановок подписок будет (map prepend (permute sublist)). Теперь определение новой функции preend для каждого элемента может быть чрезмерным - тем более, что все они имеют одинаковую форму. Поэтому лучше использовать только лямбду, которая фиксирует значение рассматриваемого элемента. Тогда желаемая операция будет (map (lambda (j) (cons element j)) (permute sublist)). Теперь мы хотим применить эту операцию к каждому элементу списка, а способ сделать это - использовать другую карту, дающую:

(map (lambda (element)
       (lambda (j) (cons element j) (permute sublist)))
     list)

Теперь это выглядит хорошо, но есть проблема: каждый этап рекурсии принимает отдельные элементы и превращает их в список. Это хорошо для списков длины 1, но для более длинных списков он повторяется для каждого рекурсивного вызова, и мы получаем очень глубоко вложенные списки. Мы действительно хотим сделать все эти списки на одной и той же основе, и это точно то, о чем заботится (apply append ...). И это почти вся эта линия. Единственное, чего не хватает, - это то, как создается подсписчик в первую очередь. Но это также легко - мы просто используем remove, так что sublist = (remove element list). Соединяя все, и у нас есть

(apply append (map (lambda (i)
                      (lambda (j) (cons i j))
                      (permute (remove i lst)))
                    lst))

. Основной случай заботится о случае длины = 1, и все остальные могут быть найдены там