How to get all necklaces without the full permutations' set?

Question

There are previous posts, such as Delete duplicates from list of lists as if on a necklace, that give a way to find all necklaces from a set of lists. The methods presented there work well for a small list dimension N.

For example, if N = 3 and if I work with two elements, 0 and 1, then I technically create the set: $$\{\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 0\}, \{0, 1, 1\}, \{1, 0, 0\}, \{1, 0, 1\}, \{1, 1, 0\}, \{1, 1, 1\}\}$$ and then select only those that are inequivalent under rotations: $$\{\{0, 0, 0 \}, \{0, 0, 1\}, \{0, 1, 1 \}, \{1, 1, 1\}\}$$

My goal is to be able to construct this set without constructing the full list of possible states.

If my understading is correct, even the faster methods presented in that question rely on the construction of the full set of states first and, then, they manipulate it to arrive to the desired result. In essence they don't use Savage's algorithm or any update of it.

My questions are:

1. Is the parallelized and compiled code of Delete duplicates from list of lists as if on a necklace comparable in performance with an optimized algorithm that constructs only the necklaces? (My understanding is that the answer is no...)

2. How would I be able to get only the necklaces for a given N? Is there any implementation of Savage's algorithm or any other more efficient algorithm in Mathematica?

Then, I want to go to 2D. Let's consider the following scenario: $$(N_x, N_y) = (3, 3)$$ I want to construct all the 2D necklaces. I assume that my 2D list is periodic across the x- and the y-dimension. This means that $$\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$ are for example equivalent (among 9 matrices with a single 1 and 8 zeros that are equivalent).

However, the following two matrices are inequivalent: $$\begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} $$

As in 1D, how would I construct all 2D necklaces for a given $(N_x, N_y)$?

---

Comment: I wanted to clearly state that the whole concept of needing to resort to the necklaces is a problem of performance... Calculating the whole tuple-set in 1D scales terribly. Calculating the necklaces however (in any problem that the only thing that matters are circularly symmetric lists) might help. This way, for example, for $N=6$ in 1D you calculate 14 necklaces instead of $2^6$ configurations. At the end, the number of necklaces scales badly too but allows for access to higher N's. The same is the goal in 2D. To be able to access system sizes that are differently not accessible via a simple calculation with Tuples.

---

Edit: Because it seems to be unclear what it is meant by necklaces, I will give some examples here.

For $N = 4$, the necklaces (distinct lists under rotations) are

$$\{0, 0, 0, 0\}, \{0, 0, 0, 1\}, \{0, 0, 1, 1\}, \{0, 1, 0, 1\}, \{0, 1, 1, 1\}, \{1, 1, 1, 1\}$$

For $N = 5$, the necklaces are

$$\{0, 0, 0, 0, 0\}, \{0, 0, 0, 0, 1\}, \{0, 0, 0, 1, 1\}, \{0, 0, 1, 0, 1\}, \{0, 0, 1, 1, 1\}, \{0, 1, 0, 1, 1\}, \{0, 1, 1, 1, 1\}, \{1, 1, 1, 1, 1\}$$

For N = 6, the necklaces are

$$\{0, 0, 0, 0, 0, 0\}, \{0, 0, 0, 0, 0, 1\}, \{0, 0, 0, 0, 1, 1\}, \{0, 0, 0, 1, 0, 1\}, \{0, 0, 1, 0, 0, 1\}, \{0, 0, 0, 1, 1, 1\}, \{0, 0, 1, 0, 1, 1\}, \{0, 1, 0, 1, 0, 1\}, \{0, 0, 1, 1, 0, 1\}, \{0, 0, 1, 1, 1, 1\}, \{0, 1, 0, 1, 1, 1\}, \{0, 1, 1, 0, 1, 1\}, \{0, 1, 1, 1, 1, 1\}, \{1, 1, 1, 1, 1, 1\}$$

The intuitive (initial) algorithm to get the necklaces for any N is described in the paper by Frank Ruskey and Carla Savage, Generating Necklaces, https://people.engr.ncsu.edu/savage/AVAILABLE_FOR_MAILING/necklace_fkm.pdf

Answer 1

Here is code similar to the answer you linked to but also works for 2D (and in principle also higher dimensions):

canonicalNecklace[a_] := First[Sort[Map[RotateRight[a,#]&,
                               Tuples[Map[Range,Dimensions[a]]]]]];

allNecklaces[alphabet_,n_Integer] := allNecklaces[alphabet,{n}];
allNecklaces[alphabet_,dims:{_Integer..}] := DeleteDuplicatesBy[Map[ArrayReshape[#,dims]&,
                  Tuples[alphabet,Times@@dims]],canonicalNecklace];

Examples:

Map[MatrixForm, allNecklaces[{0,1},5]]

Map[MatrixForm, allNecklaces[{0,1},{2,2}]]

Performance discussion. In 1D with length $n$ one always has $$\text{#necklaces} \geq \frac{\text{#tuples}}{n}$$ and in 2D with dimensions $(m,n)$ one always has $$\text{#necklaces} \geq \frac{\text{#tuples}}{mn}$$ This is true regardless of the alphabet. This is because in 1D, at most $n$ tuples give the same necklace, and in 2D, at most $mn$ tuples give the same necklace. This means that the overhead of first generating all tuples and then finding necklaces is a modest factor $n$ respectively $mn$ (modest compared to the number of tuples).

This is a somewhat theoretical argument, of course different approaches can still lead to practically significant differences in performance.

Answer 2

I calculate the necklaces of length 1 to $n$ without generating permutations by using the set of length $n-1$ to generate the set of length $n$.

ClearAll[necklaces]

necklaces[n_Integer?Positive, len_Integer?Positive] :=
 NestList[
  Flatten[
    MapIndexed[{v, i} |-> Append[v, #] & /@ Range[Min[First@i, n], n], #]
    , 1
    ] &
  , List /@ Range[n]
  , len - 1
  ]

necklaces[n_Integer?Positive, {len_Integer?Positive}] :=
 Last@necklaces[n, len]

necklaces takes the number of elements in the necklace, n, and the length of the necklace, len. When len provided as x_Integer then necklaces returns all sets of necklaces of lenght 1 to x. When len provided as {x_Integer} then only the set of necklaces of length x are returned. In both cases all necklace lengths are calculated but you save time of the Front End printing them if you only want the set of necklaces of length x.

Two elements with length 2; all sets.

necklaces[2, 2]

{
 {{1}, {2}}, 
 {{1, 1}, {1, 2}, {2, 2}}
}

Two elements with length 2; length 2 set.

necklaces[2, {2}]

{{1, 1}, {1, 2}, {2, 2}}

Two elements with length 4; length 4 set.

necklaces[2, {4}]

{{1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 2}, {1, 2, 2, 2}, {2, 2, 2, 2}}

Performance of sixteen elements with length 16; length 16 set.

RepeatedTiming[Length@necklaces[16, {16}]]

{0.0364033, 1816}

Four-hundredths of a second to return the 1,816 necklaces.

Performance of thirty-two elements with length 32; length 32 set.

RepeatedTiming[Length@necklaces[32, {32}]]

{0.706628, 15408}

Seven-tenths of a second to return the 15,408 necklaces.

N@UnitConvert[Quantity[MaxMemoryUsed[necklaces[32, {32}]], "Bytes"], "Megabytes"]

Quantity[59.8827, "Megabytes"]

Easy on the memory as well.

In contrast calculating tuples for sixteen elements of length 8 with Length@Tuples[Range[16], 8]] took about 5 minutes on my laptop with max memory of 275GB (only have 128GB) to generate the 4.3 billion tuples. necklaces[16, {8}] uses 0.5MB and returns the 856 necklaces instantly.

Note that you can swap NestList for Nest and drop the second definition if you do not care to return all length sets. This should be faster as Mma only has to prepare the final result to be passed to the Front End.

Hope this helps.