functional-programming - Heaps算法在Scheme中的实现(排列生成)

Question

我想在Scheme(Gambit)中实现Heap的算法。
我阅读了他的论文并查阅了很多资源，但我没有找到很多函数式语言实现。

我想至少得到可能排列的数量。
下一步是实际打印出所有可能的排列。

这是我目前所拥有的:

  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

这是 Wikipedia page 上描述的算法的一对一转录.由于该算法大量使用索引，我使用向量作为数据结构而不是列表:

(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)