7

長さ n の k-ary ネックレスは、長さ k のアルファベットからアイテムが抽出される長さ n の順序付けられたリストであり、ローテーションの下で順序付けを共有するすべてのリストの一種で辞書編集的に最初のリストです。

例: (1 2 3) と (1 3 2) は、アルファベット {1 2 3} の長さ 3 のネックレスです。

詳細: http://en.wikipedia.org/wiki/Necklace_(組み合わせ論)

これらをScheme（またはあなたが選んだLisp）で生成したいと思います。私はいくつかの論文を見つけました...
Savage - ネックレスを生成するための新しいアルゴリズム
澤田 - 一定の償却時間でブレスレットを
生成
する 主な理由は、アルファベットまたは必要な長さ (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

私は2段階のプロセスを実行します。まず、アルファベットから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 に答える
0

最初のアイデアとして、明白ではあるが非効率的なことを行うことができます: すべての組み合わせを調べて、それらがネックレスであるかどうか、つまり、要素の字句的に最小の回転であるかどうかを確認します (上記の論文の p 5 の正式な定義)。これはあなたが提案した方法に似ていますが、生成されたらすぐにすべての非ネックレスを破棄します.

それ以外は、この記事 ( http://citeseer.ist.psu.edu/old/wang90new.html )を理解する必要があると思います。

T. Wang および C. Savage 著、「ネックレスを生成するための新しいアルゴリズム」、レポート TR-90-20、ノースカロライナ州立大学コンピュータ サイエンス学部 (1990 年)。

tauそれほど難しいことではありません。説明に従って関数とsigma関数を実装し、記事で概説されている順序でそれらを適用することで、それを分解できます。

于 2008-11-05T12:47:40.297 に答える