Thuật toán đơn giản để tạo dây chuyền trong Đề án?

Question

Vòng cổ k-ary có độ dài n là danh sách thứ tự chiều dài n có các mục được vẽ từ bảng chữ cái có độ dài k, là danh sách thứ tự từ điển đầu tiên trong một danh sách tất cả các danh sách chia sẻ thứ tự theo vòng quay.

Ví dụ: (1 2 3) và (1 3 2) là các dây chuyền có chiều dài 3 từ bảng chữ cái {1 2 3}.

Thông tin thêm: http://en.wikipedia.org/wiki/Necklace_(combinatorics)

Tôi muốn tạo ra những trong Scheme (hoặc một Lisp của sự lựa chọn của bạn). Tôi đã tìm thấy một số giấy tờ ...
Savage - Một thuật toán mới cho Generating Necklaces
Sawada - Tạo Vòng tay trong Liên tục Thời gian khấu hao
Sawada - Tạo Necklaces với chuỗi con Forbidden
... nhưng mã trình bày trong số đó là mờ đục với tôi. Chủ yếu là bởi vì họ dường như không đi qua trong bảng chữ cái hoặc chiều dài (n) mong muốn. Các thủ tục đề án tôi đang tìm kiếm là của các hình thức (dây chuyền n '(a b c ...)).

Tôi có thể tạo những thứ này đủ dễ dàng bằng cách tạo danh sách k^n đầu tiên và sau đó lọc ra các vòng quay. Nhưng bộ nhớ không hiệu quả khủng khiếp ...

Cảm ơn!

Answer 1

Tôi sẽ thực hiện quy trình hai bước. Đầu tiên, hãy tìm từng kết hợp của các phần tử n từ bảng chữ cái. Sau đó, đối với mỗi kết hợp, chọn giá trị thấp nhất và tạo tất cả các hoán vị của các mục còn lại.

Chỉnh sửa: Đây là một số mã. Nó giả định rằng danh sách đầu vào đã được sắp xếp và nó không chứa các bản sao.

(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

Ví dụ: (1 2 3) và (1 3 2) là những dây chuyền có độ dài 3 từ bảng chữ cái {1 2 3}.

Bạn quên (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). Dây chuyền có thể chứa bản sao.

Nếu bạn chỉ tìm kiếm các dây chuyền có chiều dài N, được vẽ từ bảng chữ cái có kích thước N, có chứa không có bản sao, thì nó khá dễ dàng: Sẽ có (N-1)! dây chuyền và mỗi vòng cổ sẽ có dạng (1 :: perm) trong đó perm là bất kỳ hoán vị nào của {2 .. N}. Ví dụ, các dây chuyền của {1 .. 4} sẽ là (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) . Mở rộng phương pháp này để đối phó với các dây chuyền không trùng lặp có chiều dài K < N được để lại như một bài tập cho người đọc.

Nhưng nếu bạn muốn tìm dây chuyền thật, có thể chứa các phần tử trùng lặp, thì nó không đơn giản như vậy.

Answer 3

Thuật toán FKM để tạo dây chuyền. PLT Scheme. Không quá nóng về hiệu suất. Nó sẽ lấy bất cứ thứ gì làm bảng chữ cái và ánh xạ các số nội bộ lên bất cứ thứ gì bạn cung cấp. Dường như là chính xác; không đảm bảo. Tôi đã lười biếng khi dịch các vòng, vì vậy bạn có được hỗn hợp kỳ lạ này cho các vòng và thoát khỏi sự tiếp tục.

(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

Là một ý tưởng đầu tiên, bạn có thể làm những điều hiển nhiên, nhưng không hiệu quả: Bước qua tất cả kết hợp và kiểm tra xem họ là một sợi dây chuyền, ví dụ:nếu chúng là vòng xoay nhỏ nhất của các phần tử (định nghĩa chính thức trên p 5 ở trên giấy). Điều này sẽ giống như cách bạn đề xuất, nhưng bạn sẽ vứt bỏ tất cả các dây chuyền không phải ngay khi chúng được tạo ra.

Khác hơn thế, tôi nghĩ rằng bạn sẽ phải hiểu bài viết này (http://citeseer.ist.psu.edu/old/wang90new.html):

T. Wang và C. Savage, "Một thuật toán mới cho dây chuyền tạo ra," Báo cáo TR-90-20 , Khoa Khoa học Máy tính, Đại học Bang Bắc Carolina (1990).

Nó không quá khó, bạn có thể phá vỡ nó bằng cách thực hiện các chức năng tau và sigma như được mô tả và sau đó áp dụng chúng theo thứ tự được nêu trong bài viết.