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

Question

长度为n的k-ary项链是长度为n的有序列表,其项目是从长度为k的字母表中绘制的,这是按字典顺序排列的第一个列表,在所有列表中共享旋转下的排序.

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

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

我想在Scheme(或你选择的Lisp)中生成这些.我找到了一些论文......
野人 - 一种生成项目的新算法
Sawada - 在恒定摊销时间生成手镯
Sawada - 生成带有禁止的子串的项链
......但是它们中的代码对我来说是不透明的.主要是因为他们似乎没有传递字母或所需的长度(n).我正在寻找的方案程序是形式(项链n'(ab c ...)).

通过首先生成k ^ n个列表然后过滤掉旋转,我可以很容易地生成这些.但它的内存效率非常低......

谢谢!

Answer 1

我会做一个两步过程。首先，从字母表中找出 n 个元素的每种组合。然后，对于每个组合，选择最低值，并生成剩余项目的所有排列。

编辑：这是一些代码。它假设输入列表已经排序并且不包含重复项。

(define (choose n l)
  (let ((len (length l)))
    (cond ((= n 0) '(()))
          ((> n len) '())
          ((= n len) (list l))
          (else (append (map (lambda (x) (cons (car l) x))
                             (choose (- n 1) (cdr l)))
                        (choose n (cdr l)))))))

(define (filter pred l)
  (cond ((null? l) '())
        ((pred (car l)) (cons (car l) (filter pred (cdr l))))
        (else (filter pred (cdr l)))))

(define (permute l)
  (cond ((null? l) '(()))
        (else (apply append 
                     (map (lambda (x)
                             (let ((rest (filter (lambda (y) (not (= x y))) l)))
                               (map (lambda (subperm) (cons x subperm))
                                    (permute rest))))
                      l)))))

(define (necklaces n l)
  (apply
   append
   (map
    (lambda (combination)
      (map (lambda (permutation)
              (cons (car combination) permutation))
           (permute (cdr combination))))
    (choose n l))))


(display (choose 1 '(1 2 3 4 5))) (newline)
(display (choose 2 '(1 2 3 4 5))) (newline)
(display (permute '(1 2))) (newline)
(display (permute '(1 2 3))) (newline)
(display (necklaces 3 '(1 2 3 4))) (newline)
(display (necklaces 2 '(1 2 3 4))) (newline)