Хороший простой алгоритм генерации ожерелий в Схеме?

Question

K-арное ожерелье длины n - это упорядоченный список длины n, элементы которого взяты из алфавита длиной k, который является лексикографически первым списком в виде всех списков, разделяющих упорядочение по очереди.

Пример: (1 2 3) и (1 3 2) - ожерелья длиной 3 из алфавита {1 2 3}.

Дополнительная информация: http://en.wikipedia.org/wiki/Necklace_(combinatorics)

Я бы хотел сгенерировать их в Схеме (или на Лиспе по вашему выбору). Я нашел несколько бумаг ...
Savage - новый алгоритм генерации ожерелий
Савада - Создание браслетов в постоянное амортизированное время
Савада - Создание Ожерелья с Запрещенными Субструкциями
... но код, представленный в них, непрозрачен для меня. Главным образом потому, что они, кажется, не передаются ни по алфавиту, ни по желаемой длине (n). Схема процедуры, которую я ищу, имеет форму (ожерелья n '(a b c ...)).

Я могу сгенерировать их достаточно просто, сначала сгенерировав k ^ n списков, а затем отфильтровав вращения. Но это ужасно неэффективно в памяти ...

Спасибо!

Answer 1

Алгоритм FKM для создания ожерелий. Схема PLT. Не ахти на спектакле. Он возьмет что-нибудь в виде алфавита и отобразит внутренние цифры на то, что вы указали. Кажется правильным; нет гарантий. Я был ленив при переводе циклов, так что вы получите это странное сочетание циклов и продолжения escape.

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

В качестве первой идеи вы можете сделать очевидное, но неэффективное: пройтись по всем комбинациям и проверить, не являются ли они ожерельями, то есть являются ли они наименьшим вращением элементов (формальное определение на стр. 5 в статье выше) , Это было бы так, как вы предлагали, но вы бы выбросили все не ожерелья, как только они будут сгенерированы.

Кроме этого, я думаю, что вам придется понять эту статью (http://citeseer.ist.psu.edu/old/wang90new.html):

Т. Ван и С. Сэвидж, «Новый алгоритм генерации ожерелий», отчет TR-90-20, факультет компьютерных наук, Государственный университет Северной Каролины (1990).

Это не слишком сложно, вы можете разбить его, реализовав функции tau и sigma, как описано, и затем применив их в порядке, указанном в статье.

Answer 3

Пример: (1 2 3) и (1 3 2) - ожерелья длиной 3 из алфавита {1 2 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)! ожерелья, и каждое ожерелье будет иметь форму (1 :: perm), где perm - любая перестановка {2 .. N}. Например, ожерелья {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

Но если вы хотите найти настоящие ожерелья, которые могут содержать повторяющиеся элементы, то это не так просто.

Answer 4

Я бы сделал двухэтапный процесс. Сначала найдите каждую комбинацию из 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)