### Necklaces

 home1 home2  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  Book

Algorithms
glossary
Recursion
Linear
Binary
Permutations
Partition
N-Queens
N-Queens 3D
Necklaces
Self-Ref

A necklace of length `n' over an alphabet of `a' beads is invariant under rotation (but not reflection, that's bracelets apparently). We want to enumerate non-equivalent necklaces so we might as well enumerate the lexicographically least representative of each equivalence class.

### Form, |alphabet|≥1

n=[] a=[]
op:[] total=[] necklaces

Note that `(p)' indicates a periodic solution, and `.' indicates a dead-end has been encountered.

### CRSMS algorithm

```function CRSMS(n, a, s, pos, p)
// s[1..pos-1] is the partial solution, NB. 1..
{ if( pos <= n )
{ s[pos] = s[pos-p];
CRSMS(n, a, s, pos+1, p);
for( s[pos]++; s[pos] < a; s[pos]++ )
CRSMS(n, a, s, pos+1, pos);
}
else // pos > n, done
{ if( n % p == 0 )
{ var j, ln = new Array();
for(j=1; j < pos; j++) ln[j-1] = s[j];
//without the leading 0 of s[]
document.theForm.opt.value += (Count > 0 ? '\n' : '') + ln + ' ';
Count++;
document.theForm.Count.value = Count;
}
else document.theForm.opt.value += '.';
}
}//CRSMS

CRSMS(n, a, s, 1, 1);  //start
```

### References

Search the [Bib] for
Cattell c2000
or for
necklace
-- 17/4/2006, L.A.
 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 24-May-2024 07:10:29 AEST.