Схема - генерировать все различные перестановки списка

Question

Читая определенную книгу о функциональном программировании и, в частности, схемах (и Ракетах), я натолкнулся на упражнение, в котором говорится следующее: `

"Write a function 'rp' which takes, as an argument, a list 'lp' of pairs '(a . n)',
where 'a' is either a symbol or a number and 'n' is a natural number, 
and which returns the list of all the lists, whose elements are the 'a's defined by 
the pairs in 'lp', each one appearing exactly 'n' times."

По некоторым причинам это действительно крипти c , но в основном он запрашивает список всех различных перестановок списка, содержащих n умноженных на число / символ a .

Например: [[(rp '((a . 2) (b . 1))]] = '((a a b) (a b a) (b a a))

Генерировать перестановки, игнорируя часть distinct, довольно легко, поскольку существует относительно прямое рекурсивное определение:

The list of permutations of an empty list, is a list containing an empty list.
The list of permutations of 3 elements a b c is a list containing the lists of all permutations of
a and b where, for each one, c has been inserted in all possible positions.

, которое я перевел в следующем коде ракетки:

(define permut
  (lambda(ls)
    (if(null? ls) '(())
       (apply append
              (map (lambda(l) (insert_perm (car ls) l))
                   (permut (cdr ls)))))))

(define insert_perm
  (lambda(x ls)
    (if(null? ls) (list (list x))
       (cons (cons x ls)
             (map (lambda(l) (cons (car ls) l))
                  (insert_perm x (cdr ls)))))))

Это работает, но не возвращает различных перестановок. С учетом дубликатов мне кажется намного сложнее. Есть ли простая модификация случая простой перестановки, которую я не вижу? Является ли решение совершенно другим? Любая помощь будет оценена.

Answer 1

Изменение довольно простое. Если у вас нет дубликата, работает следующее:

Список перестановок из 3 элементов ab c - это список, содержащий списки всех перестановок a и b, где для каждого из них c было вставлено во все возможные позиции.

С дубликатами вышеупомянутое больше не работает. Перестановка из 2 элементов a = "a", b = "b":

• "a" "b"
• "b" "a"

Теперь рассмотрим c = "a". Если вы вставите его во все возможные позиции, вы получите:

• c "a" "b" = "a" "a" "b"
• "a "c" b "=" a "" a "" b "
• " a "" b "c =" a "" b "" a "
• c "b" "a" = "a" "b" "a"
• "b" c "a" = "b" "a" "a"
• "b "" a "c =" b "" a "" a "

Поэтому вместо этого установите ограничение, что при вставке вы будете делать это только до первое вхождение того же элемента, который существует в списке, в который вы вставляете:

• c "a" "b" = "a" "a" "b" - это ХОРОШО. c предшествует первому появлению "a"
• "a" c "b" = "a" "a" "b" - это не нормально. c приходит после первого вхождения "a"
• "a" "b" c = "a" "b" "a" - это не нормально
• c "b" "a" = "a" "b" "a" - это нормально
• "b" c "a" = "b" "a" "a" - это нормально
• "b" "a" c = "b" "a" "a" - это не нормально

Это дает:

• "a" "a" "b"
• "a" "b" "a"
• "b" "a" "a"

по желанию.

Более того, вы можете видеть, что этот алгоритм является обобщением алгоритма, который не работает с дубликатами. Когда дубликатов нет, «первое вхождение» отсутствует, поэтому вы можете вставлять их везде.

---

Кстати, вот как я отформатировал бы ваш код в стиле Racket / Scheme:

(define (permut ls)
  (if (null? ls)
      '(())
      (apply append
             (map (lambda (l) (insert-perm (car ls) l))
                  (permut (cdr ls))))))

(define (insert-perm x ls)
  (if (null? ls)
      (list (list x))
      (cons (cons x ls)
            (map (lambda (l) (cons (car ls) l))
                 (insert-perm x (cdr ls))))))

Answer 2

После некоторых размышлений я придумал собственное рекурсивное определение, которое, кажется, работает. Это решение является альтернативой предложенному в ответе @Sorawee Porncharoenwase и может быть определено следующим образом:

The distinct permutations of a list containing only one kind of element 
(e.g '(a a a)) is the list itself.
if (f l) gives the list of distinct permutations (lists) of l, 
where l contains x times each distinct element el_i, 0<=i<=n 
and if ll is the list l plus one element el_i, 0<=i<=n+1 (distinct or not)
Then the distinct permutations of ll is a list containing 
all the following possible concatenations:
el_i + (f l/{el_i}), where l/{el_i} is the list l excluding its ith distinct element.

Чтобы проиллюстрировать это определение, рассмотрим следующие примеры:

The list of all distinct permutations of (a b c) is the list containing
a + {(b c) (c b)} = (a b c) (a c b)
b + {(a c) (c a)} = (b a c) (b c a)
c + {(a b) (b a)} = (c a b) (c b a)

The list of all distinct permutations of (a a b) is the list containing: 
a + {(a b) (b a)} = (a a b) (a b a)
b + {(a a)} = (b a a)

etc...

Similarly, the list of all distinct permutations of (a a b c) is: 
a + {(a b c) ...} = (a a b c) (a a c b) (a b a c) (a b c a) (a c a b) (a c b a)
b + {(a a c) ...} = (a a c) (a c a) (c a a)
c + {(a a b) ...} = (a a b) (a b a) (b a a)

Это приводит к следующей реализации:

(define unique_perm
  (lambda(ls)
    (if (= (length ls) 1)
        (list (build-list (cdar ls) (const (caar ls))))
        (apply append (map (lambda(p) (map (lambda(l) (cons (car p) l)) (unique_perm (update_ls ls p)))) ls)))))

(define update_ls
  (lambda(ls p)
    (cond ((null? ls) ls)
          ((equal? (caar ls) (car p))
           (if (= (- (cdar ls) 1) 0)
               (cdr ls)
               (cons (cons (caar ls) (- (cdar ls) 1)) (cdr ls))))
          (else (cons (car ls) (update_ls (cdr ls) p))))))

Пример:

> (unique_perm_2 '((a . 3) (b . 2)))
'((a a a b b) (a a b a b) (a a b b a) (a b a a b) (a b a b a) (a b b a a) (b a a a b) (b a a b a) (b a b a a) (b b a a a))