Как я генерирую все перестановки определенного размера с повторениями в Схеме?
Я изучаю Схему, и я пытаюсь генерировать перестановки с повторениями определенного размера.
Например, данный n=4 и набор S = {a, b, c, d, e, f}, я хотел бы генерировать все возможные перестановки: {a, a, a}, {a, a, a, b}..., {a, a, a, f}, {a, a, b}, {a, a, b, b}..., {a, a, b, f}... {f, a, a}, {f, a, a, b}..., {f, a, a, f}... {f, f, f, f}.
Проблема состоит в том, что я не могу понять, как выбрать 4 времена и помнить, что я выбрал его 4 раза, затем выберите 3 времена и 'b' одно время, и помните все это, таким образом, я не выбираю его снова.
Я знаю, что эти виды проблем лучше всего решены с рекурсивными алгоритмами, но это просто делает все более сложным, как, как делают я помню в рекурсии, каким элементам выбрали меня.
Я не знаю, как приблизиться к этой проблеме вообще. Я был бы очень рад, если бы кто-то выписал мыслительный процесс решения этой проблемы. Я ценил бы его очень!
Пожалуйста, помогите мне.
Спасибо, Boda Cydo.
2 ответа
Хорошо бы начать с интерфейса процедуры и ожидаемых результатов. Ваша процедура будет называться (permutations size elements) и должна вернуть список перестановок элементов в ELEMENTS, каждая перестановка будет длиной SIZE элементов. На рисунке вы собираетесь представить "перестановку" в виде списка. Поэтому если вы вызовете (permutations 1 '(a b c)), то на выходе получите ((a) (b) (c)).
Итак, хитрость рекурсивных процедур заключается в том, что вы должны выяснить, что такое базовое условие, на которое вы можете легко ответить, и рекурсивный шаг, на который вы можете ответить, изменив решение более простой задачи. Для ПЕРМУТАЦИЙ выясним, что рекурсивный шаг будет включать уменьшение SIZE, поэтому базовым шагом будет, когда SIZE равен 0, а ответом будет список перестановок нулевой длины, т.е. (()).
Чтобы ответить на рекурсивный шаг, нужно выяснить, что нужно сделать с результатом для размера N - 1, чтобы получить результат для размера N. Для этого можно выписать несколько ожидаемых результатов для малого N и посмотреть, сможете ли вы обнаружить закономерность:
ELEMENTS = (a b) SIZE (PERMUTATIONS SIZE ELEMENTS) 0 ( () ) 1 ( (a) (b) ) 2 ( (a a) (a b) (b a) (b b) ) 3 ( (a a a) (a a b) (a b a) (a b b) (b a a) ... )
Итак, по сути, вы хотите сделать следующее: учитывая R = (перестановки n элементов), вы можете получить (перестановки (+ n 1) элементов), взяв каждую перестановку P в R, а затем для каждого элемента E в ELEMENTS приписать E к P, чтобы создать новую перестановку, и собрать их список. И мы можем сделать это с помощью вложенных MAP:
(define (permutations size elements)
(if (zero? size)
'(())
(flatmap (lambda (p) ; For each permutation we already have:
(map (lambda (e) ; For each element in the set:
(cons e p)) ; Add the element to the perm'n.
elements))
(permutations (- size 1) elements))))
Я использую FLATMAP для внешнего отображения, потому что внутренняя MAP создает списки новых перестановок, и мы должны сложить эти списки вместе, чтобы создать один большой плоский список перестановок, который нам нужен.
Конечно, это все при условии, что вы знаете и хорошо разбираетесь в операциях с последовательностью, таких как MAP. В противном случае будет очень трудно придумать элегантное решение, как я только что сделал здесь.
Подсказка: вы можете использовать параметры рекурсивного вызова, чтобы «запомнить», что сделали другие рекурсивные вызовы. ;)