создание перестановки списка в схеме

Question

Я пытаюсь написать функцию, которая создает перестановку списка, используя только основные конструкции списка (минусы, пустые, сначала, остальные). Я думаю о том, чтобы вставить первое значение списка всюду в рекурсивном вызове остальной части списка, но у меня проблемы с базовым случаем.

Мой код:

(define (permutation lst) 
    (cond 
     [(empty? lst) (cons empty empty)] 
     [else (insert_everywhere (first lst) (permutation (rest lst)))])) 

(перестановка (список 1 2)) дает мне (список 1 2 2 1 пустой пустой). Есть ли что-нибудь, что я могу сделать, чтобы создать местозаполнитель (например, пустой) между различными комбинациями, но не использовать программу для интерпретации заполнителя в качестве элемента в списке?

Это мой базовый кейс справа?

Спасибо!

Answer 1

Алгоритм перестановок не так прост, как вы себе представляете, это действительно очень сложно написать только в терминах основных операций с списком, которые вы упомянули, если только вы не написали свои собственные помощники, которые отражают встроенные функции, такие как как map, append (но почему бы не использовать встроенные модули в первую очередь?).

Чтобы получить представление о том, что необходимо сделать, ознакомьтесь с кодом Rosetta page, описывающим несколько возможных решений, посмотрите на ссылки Схемы или Ракетки. Вот адаптация одной из реализаций с нуля, показанных на связанную странице - и, кроме основных операций списка упомянутых в вопросе, он использует append и map:

(define (permutations s) 
    (cond [(empty? s) empty] 
     [(empty? (rest s)) (list s)] 
     [else 
     (let splice [(l '()) (m (first s)) (r (rest s))] 
      (append 
      (map (lambda (x) (cons m x)) 
       (permutations (append l r))) 
      (if (empty? r) 
       empty 
       (splice (cons m l) (car r) (cdr r)))))])) 

Посмотрите, как это работает:

(permutations '(1 2 3)) 
=> '((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 2 1) (3 1 2)) 

Answer 2

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

(define (f n k) ; lists will be from 0..(n-1) 
    (define pl '()) ; all permutations list; 
    (let loop ((ol '())) ; one permutation list; 
    (define a (random n)) ; 0 to n-1 
    (if (member a ol) (loop ol) 
     (begin (set! ol (cons a ol)) 
       (if (< (length ol) k) (loop ol) 
        (if (member ol pl) (loop '()) 
         (begin (set! pl (cons ol pl)) 
           (if(< (length pl) 
            (/(factorial n) 
             (factorial (- n k)))) 
           (loop '()) 
           pl)))))))) 

(выше код в Racket - производное Scheme)

Тестирование:

(f 3 2) 
(f 3 3) 
(f 4 2) 

Выход:

'((2 1) (1 0) (0 1) (0 2) (1 2) (2 0)) 
'((2 1 0) (1 0 2) (0 1 2) (1 2 0) (0 2 1) (2 0 1)) 
'((2 1) (3 0) (1 0) (1 3) (3 2) (2 3) (0 3) (0 1) (0 2) (2 0) (1 2) (3 1))