7

长度为 n 的 k-ary 项链是长度为 n 的有序列表，其项目来自长度为 k 的字母表，它是所有列表中共享旋转排序的排序中的字典第一个列表。

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

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

我想在 Scheme（或您选择的 Lisp）中生成这些。我找到了一些论文...
Savage - A New Algorithm for Generate Necklaces
Sawada - 在恒定摊销时间内生成手链
Sawada - 生成带有禁止子串的项链
...但是其中提供的代码对我来说是不透明的。主要是因为它们似乎没有传递所需的字母或长度（n）。我正在寻找的方案程序的形式是 (necklaces n '(ab c...))。

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

谢谢！

4

4 回答 4

3

用于生成项链的 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))
于 2008-11-04T20:25:43.713 回答
0

作为第一个想法，您可以做显而易见但效率低下的事情：逐步检查所有组合并检查它们是否是项链，即它们是否是元素的词汇最小旋转（上述论文中第 5 页的正式定义）。这就像您提议的方式，但是您将在生成所有非项链后立即丢弃它们。

除此之外，我认为您必须了解这篇文章（http://citeseer.ist.psu.edu/old/wang90new.html）：

T. Wang 和 C. Savage，“生成项链的新算法”，报告 TR-90-20，北卡罗来纳州立大学计算机科学系（1990 年）。

这不是太难，您可以通过实现描述的tauandsigma函数来分解它，然后按照文章中概述的顺序应用它们。

于 2008-11-05T12:47:40.297 回答
0

我会做一个两步的过程。首先，从字母表中找到 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)
于 2008-11-04T19:12:33.877 回答
0

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

你忘了 (1 1 1) (1 1 2) (1 1 3) (1 2 2) (1 3 3) (2 2 2) (2 2 3) (2 3 3) (3 3 3)。项链可以包含重复项。

如果您只是在寻找长度为 N 的项链，从大小为 N 的字母中提取，并且不包含重复项，那么这很容易：会有 (N-1) 个！项链，每条项链的形式都是 {2 .. N}(1 :: perm)的perm任意排列。例如，{1 .. 4} 的项链将是 (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) . 扩展此方法以处理长度为 K < N 的无重复项链作为练习留给读者。

但如果你想找到可能包含重复元素的真正项链，那就没那么简单了。

于 2008-11-04T20:21:05.890 回答