Necklaces

LA home
Computing
Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Subgraphs
  Brackets
  Self-Ref
  Necklaces

also see
  factors

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

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 for
Cattell c2000
or for
necklace
-- L.A.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Monday, 29-Nov-2021 21:11:37 EST.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.