5
$\begingroup$

Consider the following classic problem in combinatorics: how many neckleces with $n$ black/white beds are there up to rotations? You can formulate the question in the language of group theory: acting with $\mathbb{Z}/n\mathbb{Z}$ on $\{0,1\}^n$ by circular shift, how many orbits are there?

I'm looking for an algorithm that lists representatives for the orbits. In particular I'd like to have the source code of a working, self-contained implementation of it (or a precise link to the relevant code in some big package as GAP).

This question looks similar in nature, but the particular problem it's different and I don't see a natural way to adapt the answer given there.

  • 0
    I'm hoping there's a more efficient method in GAP, but you can do it brute-force by `n:=5;; g:=CyclicGroup(IsPermGroup,n);; OrbitsDomain(g,Tuples([0,1],n),Permuted);` This will, in fact, partition the necklaces into orbits.2012-11-02
  • 0
    @Douglas: I'm interested in how the algorithm works, do you know how GAP does the work?2012-11-02
  • 0
    Not really, I'm afraid. If you're after a general algorithm, however, you might get some mileage out of the paper "Isomorph-free exhaustive generation" by Brendan McKay; here: cs.anu.edu.au/~bdm/papers/orderly.pdf.2012-11-02
  • 0
    In the example by @DouglasS.Stones GAP uses `OrbitsDomain` method for arbitrary domains from `gap4r6p5/lib/oprt.gi`. Since GAP is open-source, you can look at it (search for `"for arbitrary domains"` substring in that file). Please ask [GAP Forum](http://www.gap-system.org/Contacts/Forum/forum.html) or [GAP Support](http://www.gap-system.org/Contacts/People/supportgroup.html) if you will be interested in further details.2013-11-06

2 Answers 2