Как мне сгенерировать все перестановки определенного размера с повторениями в Схеме? - PullRequest
Новая
       18

Как мне сгенерировать все перестановки определенного размера с повторениями в Схеме?

6 голосов
/ 05 июля 2010

Я изучаю Схему и пытаюсь генерировать перестановки с повторениями определенного размера.

Например, если дано n = 4 и задано S = {a, b, c, d, e, f}, Я хотел бы генерировать все возможные перестановки: {a, a, a, a}, {a, a, a, b}, ..., {a, a, a, f}, {a, a,Ь, а}, {а, а, Ь, Ь}, ..., {а, а, б, е}, ... {е, а, а, а}, {е, а, а, б} ..., {f, a, a, f}, ... {f, f, f, f}.

Проблема в том, что я не могу понять, как выбрать 'a' 4раз, и помните, что я выбрал его 4 раза, затем выберите «а» 3 раза и «б» один раз, и запомните все это, чтобы я не выбрал его снова.

Я знаю, чтоПодобные проблемы лучше всего решать с помощью рекурсивных алгоритмов, но это просто усложняет все, например, как я помню в рекурсии, какие элементы я выбрал.

Я не знаю, как к этому подойтипроблема вообще.Я был бы очень рад, если бы кто-то выписал мыслительный процесс решения этой проблемы.Я был бы очень признателен!

Пожалуйста, помогите мне.

Спасибо, Бода Кидо.

Ответы [ 3 ]

4 голосов
/ 05 июля 2010

Хорошо начать с интерфейса процедуры и ожидаемых результатов.Ваша процедура будет называться (permutations size elements) и, как ожидается, вернет список перестановок элементов в ELEMENTS, каждая перестановка будет длинной SIZE элементов.На рисунке вы будете представлять «перестановку» в виде списка.Поэтому, если бы вы позвонили (permutations 1 '(a b c)), вы ожидали бы вывод ((a) (b) (c)).

Итак, хитрость в рекурсивных процедурах заключается в том, что вы должны выяснить, каково базовое условие, на которое вы можете легко ответить,рекурсивный шаг, на который вы можете ответить, изменив решение более простой задачи.Для PERMUTATIONS, рисунок рекурсивный шаг будет включать в себя уменьшение размера, поэтому базовый шаг будет, когда размер равен 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 = (permutations n elements), вы можете получить (permutations (+ n 1) elements), взяв каждую перестановку 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.Если вы этого не сделаете, было бы очень сложно придумать элегантное решение, как я только что сделал здесь.

1 голос
/ 05 ноября 2012

Вот еще одна версия: я использовал уменьшение, а не flatmap.Я написал это в MIT-scheme. 

(define (per s)

  (define (ins c before after)
    (if (null? after)
        (list (append before (list c)))
        (append (list (append before (list c) after))
                (ins c
                     (append before (list (car after)))
                     (cdr after)))))
  (define (iter l)
    (cond ((null? l)
           '(()))
          (else
           (let ((rest (iter (cdr l))))
             (reduce-left append
                          ()
                          (map (lambda (x) (ins (car l) () x) )
                               rest))))))
  (iter s))

(per '(1 3 2 4))
0 голосов
/ 05 июля 2010

Подсказка: вы можете использовать параметры для рекурсивного вызова, чтобы «запомнить», что сделали другие рекурсивные вызовы.;)

...