scheme - 在 Scheme 中生成项链的好简单算法？

Question

长度为 n 的 k 元项链是一个长度为 n 的有序列表，其项目是从长度为 k 的字母表中抽取的，它是所有共享轮换排序的列表中按字典顺序排列的第一个列表。

例子:
(1 2 3) 和 (1 3 2) 是字母 {1 2 3} 中长度为 3 的项链。

更多信息:
http://en.wikipedia.org/wiki/Necklace_(combinatorics)

我想在 Scheme(或您选择的 Lisp)中生成这些。我找到了一些文件...
Savage - 生成项链的新算法
Sawada - 在固定的摊销时间内生成手链
Sawada - 用禁止子串生成项链
...但其中提供的代码对我来说是不透明的。主要是因为它们似乎没有传入所需的字母表或长度 (n)。我正在寻找的计划程序的形式是 (necklaces n '(a b c...))。

我可以通过首先生成 k^n 列表然后过滤掉旋转来轻松生成这些。但它的内存效率非常低......

谢谢!

Answer 1

用于生成项链的 FKM 算法。 PLT 计划。表演上没那么火爆。它会将任何内容作为字母表并将内部数字映射到您提供的任何内容上。似乎是正确的；没有保证。我在翻译循环时很懒惰，所以你得到了 for 循环和转义延续的奇怪组合。

(require srfi/43)

(define (gennecklaces n alphabet)
  (let* ([necklaces '()]
         [alphavec (list->vector alphabet)]
         [convert-necklace
          (lambda (vec)
            (map (lambda (x) (vector-ref alphavec x)) (cdr (vector->list vec))))]
         [helper
          (lambda (n k)
            (let ([a (make-vector (+ n 1) 0)]
                  [i n])
              (set! necklaces (cons (convert-necklace a) necklaces))
              (let/ec done
                (for ([X (in-naturals)])
                  (vector-set! a i (add1 (vector-ref a i)))
                  (for ([j (in-range 1 (add1 (- n i)))])
                    (vector-set! a (+ j i)
                                 (vector-ref a j)))
                  (when (= 0 (modulo n i))
                    (set! necklaces (cons (convert-necklace a) necklaces)))
                  (set! i n)
                  (let/ec done
                    (for ([X (in-naturals)])
                      (unless (= (vector-ref a i)
                                 (- k 1))
                        (done))
                      (set! i (- i 1))))
                  (when (= i 0)
                    (done))))))])
    (helper n (length alphabet))
    necklaces))