Реализация алгоритма кучи в схеме (генерация перестановки)

Question

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

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

Вот что у меня так далеко:

  3 (define (heap lst n)
  4   (if (= n 1)
  5     0
  6     (let ((i 1) (temp 0))
  7       (if (< i n)
  8         (begin
  9           (heap lst (- n 1))
 10           (cond
 11             ; if even:  1 to n -1 consecutively cell selected
 12             ((= 0 (modulo n 2))
 13               ;(cons (car lst) (heap (cdr lst) (length (cdr lst)))))
 14               (+ 1 (heap (cdr lst) (length (cdr lst)))))
 15
 16             ; if odd:   first cell selectd
 17             ((= 1 (modulo n 2))
 18               ;(cons (car lst) (heap (cdr lst) (length (cdr lst)))))
 19               (+ 1 (heap (car lst) 1)))
 20           )
 21         )
 22         0
 23       )
 24     )
 25   )
 26 )
 27
 28 (define myLst '(a b c))
 29
 30 (display (heap myLst (length myLst)))
 31 (newline)

Я уверен, что это далеко, но это так близко, как я мог получить.
Любая помощь будет отличной, спасибо.

Answer 1

Вот транскрипция алгоритма 1: 1, описанная на странице Википедии. Поскольку алгоритм интенсивно использует индексирование, я использовал вектор в качестве структуры данных, а не списка:

(define (generate n A)
  (cond
    ((= n 1) (display A)
             (newline))
    (else    (let loop ((i 0))
               (generate (- n 1) A)
               (if (even? n)
                   (swap A i (- n 1))
                   (swap A 0 (- n 1)))
               (if (< i (- n 2))
                   (loop (+ i 1))
                   (generate (- n 1) A))))))

и swap вспомогательная процедура:

(define (swap A i1 i2)
  (let ((tmp (vector-ref A i1)))
    (vector-set! A i1 (vector-ref A i2))
    (vector-set! A i2 tmp)))

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

Gambit v4.8.4

> (generate 3 (vector 'a 'b 'c))
#(a b c)
#(b a c)
#(c a b)
#(a c b)
#(b c a)
#(c b a)