Good simple algorithm for generating necklaces in Scheme?

Question

A k-ary necklace of length n is an ordered list of length n whose items are drawn from an alphabet of length k, which is the lexicographically first list in a sort of all lists sharing an ordering under rotation.

Example: (1 2 3) and (1 3 2) are the necklaces of length 3 from the alphabet {1 2 3}.

More info: http://en.wikipedia.org/wiki/Necklace_(combinatorics)

I'd like to generate these in Scheme (or a Lisp of your choice). I've found some papers...
Savage - A New Algorithm for Generating Necklaces
Sawada - Generating Bracelets in Constant Amortized Time
Sawada - Generating Necklaces with Forbidden Substrings
...but the code presented in them is opaque to me. Mainly because they don't seem to be passing in either the alphabet or the length (n) desired. The scheme procedure I'm looking for is of the form (necklaces n '(a b c...)).

I can generate these easy enough by first generating k^n lists and then filtering out the rotations. But it's terribly memory-inefficient...

Thanks!

Answer 1

I would do a two step process. First, find each combination of n elements from the alphabet. Then, for each combination, pick the lowest value, and generate all permutations of the remaining items.

Edit: Here is some code. It assumes that the input list is already sorted and that it contains no duplicates.

(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

Example: (1 2 3) and (1 3 2) are the necklaces of length 3 from the alphabet {1 2 3}.

You forgot (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). Necklaces can contain duplicates.

If you were only looking for necklaces of length N, drawn from an alphabet of size N, that contain no duplicates, then it's pretty easy: there will be (N-1)! necklaces, and each necklace will be of the form (1 :: perm) where perm is any permutation of {2 .. N}. For example, the necklaces of {1 .. 4} would be (1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2). Extending this method to deal with no-duplicates necklaces of length K < N is left as an exercise for the reader.

But if you want to find real necklaces, which may contain duplicate elements, then it's not so simple.

Answer 3

The FKM algorithm for generating necklaces. PLT Scheme. Not so hot on the performance. It'll take anything as an alphabet and maps the internal numbers onto whatever you provided. Seems to be correct; no guarantees. I was lazy when translating the loops, so you get this weird mix of for loops and escape continuations.

(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

How odd. I logged in with Open ID (despite the first two vendors I tried returning errors), and I still can't reply to comments on my own submission, nor edit my submission. I'd have to really apply myself to break a system this badly.

That said, yes, sorry, I forgot about the other 8 necklaces. Necklaces are really what I want.

Edit: Hmph! I can't even vote you up, Jay. Man, this site is oppressive. Thanks to everyone who replied.

I don't know what let/ec does but I'll look it up. Too bad about the imperative style and side-effects...

Answer 5

As a first idea, you can do the obvious, but inefficient: step through all combinations and check if they are a necklace, i.e. if they are the lexically smallest rotation of the elements (formal definition on p 5 in above paper). This would be like the way you proposed, but you would throw away all non-necklaces as soon as they are generated.

Other than that, I think that you will have to understand this article (http://citeseer.ist.psu.edu/old/wang90new.html):

T. Wang and C. Savage, "A new algorithm for generating necklaces," Report TR-90-20, Department of Computer Science, North Carolina State University (1990).

It is not too hard, you can break it down by implementing the tau and sigma functions as described and then applying them in the order outlined in the article.