1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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]]

enter image description here

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

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ Thank you very much for adapting that code for the 2d case. However, I have some problems... First of all, this code performs a bit slower than the cited one. The problems start from around n=17 in the 1D case and the margin keeps increasing. So, for the 1D case this is not a performant solution. Is there a possibility that you understand well and could adapt the parallel evaluated and compiled code? (I am not sure I understand it really well to be able to do so...). $\endgroup$
    – Kostas
    Nov 21, 2022 at 20:48
  • $\begingroup$ The 2nd (major) concern that I have is about the time scaling for the 2D case. Calculating the necklaces even for a $5 \times 5$ lattice is impossible at my laptop. The whole reason behind the calulation of necklaces is to simpify the calculations for the basis states of the 2D system. If the calculation of the 2D necklaces is realistically impossible for a 6x6 lattice, there is no reason to resort to necklaces... So, again I have a problem regarding performance (as also stated in the question)... $\endgroup$
    – Kostas
    Nov 21, 2022 at 20:49
  • $\begingroup$ You are welcome. I had no intention to compete with the answers in the thread you linked to. I just wanted to provide some 2D code, and point out that generating all tuples is not in principle incredibly bad (since you did not point that out) but have no interest in tuning performance further. $\endgroup$
    – user293787
    Nov 21, 2022 at 20:55
  • $\begingroup$ Thanks a lot for the answer indeed. The problem with generating the 2D necklaces this way is that it is more efficient to use the full tuples in any subsequent code and do all the manipulations on the full set. Otherwise, we are restricted to 4x4, max 5x5 lattice sizes... The question was more focused on an efficient (performant) solution (maybe not clearly stated...fixed though!). This is why I stated in the question "without getting the full permutations' set" because this is the whole concept of needing the necklaces in some calculations... to allow me to go to higher system sizes :) $\endgroup$
    – Kostas
    Nov 21, 2022 at 21:10
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ A first comment...I needed to change the command |-> with Function[x, body] because otherwise Mathematica gave a syntax error...do you know maybe why? $\endgroup$
    – Kostas
    Nov 22, 2022 at 1:49
  • $\begingroup$ @KonstantinosSfairopoulos Which version of Mma are you using? The |-> syntax was added in version 12.2 $\endgroup$
    – Edmund
    Nov 22, 2022 at 1:53
  • $\begingroup$ Yes, I feared that...I have 11.3. No worries about that. It was simple to fix:) $\endgroup$
    – Kostas
    Nov 22, 2022 at 2:06
  • $\begingroup$ Regarding the actual algorithm I have some issues...Regarding performance, this is simply outstanding!! However, this algorithm still doesn't calculate the necklaces. There are many more that cannot be found with your function unfortunately...(please see my edit) $\endgroup$
    – Kostas
    Nov 22, 2022 at 2:07
  • $\begingroup$ @KonstantinosSfairopoulos Ah, I see. I'll have a think on it. $\endgroup$
    – Edmund
    Nov 22, 2022 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.