¿Buen algoritmo simple para generar collares en Scheme?

Question

Un collar k-ary de longitud n es una lista ordenada de longitud n cuyos elementos se extraen de un alfabeto de longitud k, que es la lista lexicográficamente primera en una especie de todas las listas que comparten un pedido en rotación.

Ejemplo: (1 2 3) y (1 3 2) son los collares de longitud 3 del alfabeto {1 2 3}.

Más información: http://en.wikipedia.org/wiki/Necklace_(combinatorics)

me gustaría para generar éstos en el Esquema (o un Lisp de su elección). He encontrado unos papeles ...
Savage - Un nuevo algoritmo para generar Collares
Sawada - Generación de pulseras en Constante de tiempo amortizado
Sawada - Collares electrógenos con Subcadenas Forbidden
... pero el código que figura en ellos es opaco para mi Principalmente porque no parecen estar pasando ni en el alfabeto ni en la longitud (n) deseada. El procedimiento de esquema que estoy buscando es de la forma (collares n '(a b c ...)).

Puedo generar esto de manera fácil generando listas k^n y luego filtrando las rotaciones. Pero es terriblemente ineficaz en la memoria ...

¡Gracias!

Answer 1

Haría un proceso de dos pasos. Primero, encuentre cada combinación de n elementos del alfabeto. Luego, para cada combinación, elija el valor más bajo y genere todas las permutaciones de los elementos restantes.

Editar: Aquí hay algunos códigos. Asume que la lista de entrada ya está ordenada y que no contiene duplicados.

(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

Ejemplo: (1 2 3) y (1 3 2) son los collares de longitud 3 del alfabeto {1 2 3}.

Olvidó (1 1 1) (1 1 2) (1 1 2) (1 3 3) (2 2 2) (2 3 3) (3 3 3). Los collares pueden contener duplicados.

Si solo estabas buscando collares de longitud N, extraídos de un alfabeto de tamaño N, que contienen no duplicados, entonces es bastante fácil: ¡habrá (N-1)! collares, y cada collar tendrá la forma (1 :: perm) donde perm es cualquier permutación de {2 .. N}. Por ejemplo, los collares de {1 .. 4} serían (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) . Extendiendo este método para tratar collares sin duplicados de longitud K < N se deja como un ejercicio para el lector.

Pero si quieres encontrar collares reales, que pueden contener elementos duplicados, entonces no es tan simple.

Answer 3

El algoritmo de FKM para generar collares. Esquema PLT. No hace tanto calor en el rendimiento. Tomará cualquier cosa como un alfabeto y correlaciona los números internos con lo que usted proporcionó. Parece ser correcto; sin garantías Fui flojo cuando traduje los bucles, así que obtienes esta extraña mezcla de bucles for y escape de continuación.

(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

Como primera idea, que puede hacer lo que es obvio, pero ineficiente: paso a través de todas las combinaciones y comprobar si son un collar, es decir,si son la rotación léxicamente más pequeña de los elementos (definición formal en p 5 en el artículo anterior). Esto sería como lo propusiste, pero tirarías todos los no collares tan pronto como se generen.

Aparte de eso, creo que va a tener que entender este artículo (http://citeseer.ist.psu.edu/old/wang90new.html):

T. Wang y C. Savage, "Un nuevo algoritmo para la generación de collares," Informe TR-90-20 , Departamento de Ciencias de la Computación, North Carolina State University (1990).

No es demasiado difícil, puede descomponerlo implementando las funciones tau y como se describe y luego aplicándolas en el orden descrito en el artículo.