|
|
A necklace of length ‘n’
over an alphabet of ‘a’ beads is invariant under rotation
(but not necessarily under 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
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 for
- Cattell c2000
- or for
- necklace
|
-- L.A.
|
|
|