Scheme에서 목걸이를 생성하는 좋은 간단한 알고리즘은 무엇입니까?

Question

길이가 n 인 k-ary 목걸이는 길이가 k 인 알파벳에서 그려지는 항목의 길이가 n 인 순서 목록입니다. 회전하는 순서를 공유하는 모든 목록의 정렬 식 사전 식 목록입니다.

예 : (1 2 3) 및 (1 3 2)은 알파벳 {1 2 3}에서 길이 3 인 목걸이입니다.

상세 정보 : http://en.wikipedia.org/wiki/Necklace_(combinatorics)

내가 계획에이를 생성하고 싶습니다

(또는 당신의 선택의 리스프). 생성 목걸이
사와다위한 새로운 알고리즘 - - 나는 몇 가지 서류 ...
야만인을 발견했습니다 일정한 상각 시간에 생성 팔찌를
사와다 - 생성 목걸이 금지 하위 문자열
...하지만 그들에 제시된 코드가와 나에게 불투명하다. 주로 알파벳이나 길이 (n)로 전달되지 않는 것 같습니다. 내가 찾고있는 절차는 다음과 같은 형식입니다 (목걸이 n '(a b 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) 

Answer 2

예 (1 2 3) (1 2 3) 알파벳 {1 2 3}에서 길이 3의 목걸이이다.

당신은 (1 1 1) (1 2) (1 3) (1 2) (1 3/3) (2/2 2) (2 3) (2 3 3) (3 잊고 3 3). 목걸이는 중복을 포함 할 수 있습니다.

크기 N의 알파벳으로 그려지는 길이 N의 목걸이를 찾고 있는데, 이없고 중복이없는 목걸이를 찾으신다면 (N-1)이 될 것입니다! 목걸이 및 각 목걸이의 형태는 (1 :: perm)입니다. 여기서 perm은 임의의 순열 {2 .. N}입니다. 예를 들어 {1 .. 4}의 목걸이는 (1 2 3 4) (1 2 4 3) (1 3 4 2) (1 4 2 3) (1 4 3 2) . 이 방법을 확장하여 길이가 K < N 인 중복 목걸이를 다루는 것은 독자의 연습 과제로 남겨 둡니다.

하지만 중복 된 요소가 포함될 수있는 실제 목걸이를 찾으려면 그다지 간단하지 않습니다.

Answer 3

목걸이 생성을위한 FKM 알고리즘. PLT 제도. 성능에 너무 열광적이지 않습니다. 그것은 무엇이든을 알파벳으로 취하고 내부 숫자를 당신이 제공 한 것에 매핑합니다. 올바른 것으로 보인다. 보증은 없다. 나는 루프를 번역 할 때 게으르다. 그래서 루프와 탈출구를위한 이상한 혼합을 얻는다.

(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)) 

Answer 4

첫 번째 아이디어는 분명하지만 비효율적입니다. 모든 조합을 단계별로 실행하여 목걸이인지 확인하십시오.어휘 적으로 가장 작은 요소의 회전 인 경우 (위의 5 장의 공식 정의). 이것은 당신이 제안한 방식과 같을 것입니다. 그러나 목걸이가 아닌 모든 목걸이는 생성되는 즉시 버릴 것입니다.

T. 왕과 C. 야만인, "생성 목걸이를위한 새로운 알고리즘,"보고서 TR-90-20 : 그 외에는

, 나는이 문서 (http://citeseer.ist.psu.edu/old/wang90new.html)을 이해해야 것이라고 생각 , 노스 캐롤라이나 주립 대학 컴퓨터 과학과 (1990).

너무 어렵지 않으므로 설명한대로 tau 및 sigma 기능을 구현 한 다음 기사에 설명 된 순서대로 적용하여 문제를 해결할 수 있습니다.