3

ヒープのアルゴリズムをScheme(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)

私はこれがかなり離れていると確信していますが、私が得ることができる限り近いです.
どんな助けでも素晴らしいでしょう、ありがとう。

4

1 に答える 1

6

これは、ウィキペディアのページで説明されているアルゴリズムを 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)
于 2016-03-09T20:57:53.860 に答える