0
$\begingroup$

I asked a question in a previous post about enumerating all possible k-ary bracelets with certain positions fixed to a specific bead/character. I asked a few mathematicians, and it seems its quite difficult to do so in a reasonable way.

However, it turns out that I am only looking for necklaces, not bracelets. Eg I only care about rotations, not reflections.

Hopefully its ok to ask the basically the same question again, Im thinking it might be more feasible to enumerate if you only have to factor in rotations.

To restate the question, say I have k possible integers to pick from, and my program randomly picks from the set of k when generating necklaces of length n, I know I can enumerate the maximum possible unique necklaces that could be generated for n/k using the equation listed here. This is great because now I have an upper bound on my programs duration and know when to stop running if I have already found all possible unique necklaces for a given n/k

However, my program also has the option to conserve, or fix, any particular value from the set of k, at any position in the necklace. It allows this to be done for as many positions of length n that you want.

For example, given n = 4, and k = [0, 1, 2, 3, 4, 5, 6], and considering the following necklaces equivalent:

[0,0,0,1] and [1,0,0,0]

I can use the formula as mentioned here to calculate easily how many unique necklaces I can possibly generate.

But if the user of my program specifies that they want the generated necklaces to always have the value 1 at position 1 and the value 2 at position 4, eg the random necklace generator will only create sequences such as:

[1,0,0,2] or [1,6,4,2] or [1,2,3,2]

The question is: given necklaces of length n containing any selection of characters from set k with f positions in n being fixed to c different values from k, is it possible to enumerate the total unique necklaces that could be made

$\endgroup$
  • $\begingroup$ To help people pitch their answers, do you know any group theory? (Not) Burnside's lemma? Pólya enumeration theory? $\endgroup$ – Peter Taylor Dec 10 '18 at 11:02
  • $\begingroup$ Im very new to this kind of mathematics, Im actually normally a web developer who is building something to help a mate who is doing his phd. it took me ages to work out how to convert the necklace enumeration formula from that wiki article i linked into code. $\endgroup$ – Matthew Prasinov Dec 10 '18 at 11:46
  • $\begingroup$ If you want to generate a list of all the distinct necklaces then it's probably easier to skip the maths and just generate all strings which meet the additional constraints, rejecting those which have a rotation which also meets the constraints and is lexicographically smaller. But you mention "random necklace generator", so is your final goal to write some software which selects the necklaces uniformly, avoiding biases towards those which have multiple valid rotations? $\endgroup$ – Peter Taylor Dec 10 '18 at 12:40
  • $\begingroup$ i already have written the software, im looking for a mathematical formula to calculate the upper bounds of how long it should run, since it randomly generates the sequences and checks for uniqueness as it goes in a big long loop. for non-necklace sequences, and plain necklaces, i know when i have found all possible options (eg i know when to stop the loop), but also more to the point if the number of sequences requested is the same as the maximum possible, i switch to a non-random generation. $\endgroup$ – Matthew Prasinov Dec 10 '18 at 14:43
  • $\begingroup$ if however, the user requests sequences with fixed position, i have no way of knowing what the maximum possible sequences is, so cant terminate the loop with confidence, and more importantly dont know if the maximum number of sequences has been requested so as to switch from random to sequential generation $\endgroup$ – Matthew Prasinov Dec 10 '18 at 14:44
1
$\begingroup$

This isn't a full answer to the question as asked, but I hope it's a sufficient answer to the underlying question.

Partial coupon collector

Suppose there are $N$ distinct necklaces and you have a method which uniformly generates a random one. You want to select $n$ different ones. If you do so by the simple process of generating and adding to a set until the size of the set is $n$, the expected number of times you have to call the generation method is $$\frac{N}{N} + \frac{N}{N-1} + \cdots + \frac{N}{N-n+1}$$ as a truncated sum from the coupon collector problem.

Suppose you also have a method to generate the complete set of $N$ necklaces, and it is about as expensive as calling the random generation $N$ times. You can then do a partial shuffle to select $n$ of them.

At what value of $n$ should you prefer the sequential generator to the random generator? The answer is when $n > (1 - \frac{1}{e})N$. (There must be a proof of that somewhere on this site; I haven't found it, but if anyone can find one then feel free to edit, removing this parenthetical and adding a link).

For practical purposes we can approximate that as $n > \frac{2}{3}N$. Note that this implies that you can optimise your existing solution for non-necklaces and plain necklaces.

Single constraint

The single constraint that position $i$ has colour $j$ is just a constraint that there be at least one bead of colour $j$. The number of necklaces satisfying this single constraint is the number of necklaces with $k$ colours minus the number without colour $j$, so $$\frac{1}{n}\sum_{d\mid n}\varphi(d)\left( k^{\frac{n}{d}} - (k-1)^{\frac{n}{d}} \right)$$

Asymptotics of necklaces with constraints

For $n$-element necklaces over $k$ colours without constraints, the first order approximation is that there are about $\frac{1}{n} k^n$ distinct necklaces. This is easy to understand: there are $k^n$ strings of $n$ elements over $k$ symbols, and the majority of them are aperiodic so that the $n$ rotations are distinct.

If we now constrain $f > 1$ positions, the first order approximation is $k^{n-f}$. This is again easy to understand: in general, the rotations of a valid string will not satisfy all $f$ constraints. (Note: if the constraints are periodic then this argument needs modification to take account of the periodicity. E.g. if the constraints are automatically satisfied by a rotation of $\frac{n}{2}$ then the first order approximation is $\frac{1}{2}k^{n-f}$). The second-order correction is $O(k^{n-f-1})$. If $k$ is large then the $O$ would have to be hiding a large constant for $N$ to get below $\frac{2}{3}k^{n-f}$. In fact, I suspect that the second-order correction can be stated much more tightly as $O(k^{\frac{1}{2}(n-f)})$, but I haven't tried to prove this.

Putting it together: a practical approach

Calculate an upper bound $U$ using the formula for unconstrained necklaces, as a precaution for the small-$k$ case. Define an estimate $\tilde N = \min(U, k^{n-f})$ for the number of solutions, with corrections for periodicity as discussed. If $n > \frac{2}{3} \tilde N$, use sequential generation. Otherwise use random generation, but as a further precaution count the number of times you call the random generator. If the count passes e.g. $1.5 \tilde N$, abort the random generation and switch to sequential generation, logging the parameters for a more specific follow-up question.

$\endgroup$
  • $\begingroup$ holy crap thats an in-depth explanation. im not a mathematician by any stretch so it will take me a while (and lots of googling) to parse exactly what is being said here, but thank you so much for taking the time to explain it in such detail. $\endgroup$ – Matthew Prasinov Dec 11 '18 at 15:55
  • $\begingroup$ ah yep the constrainsts i believe are periodic, eg rotations of the string still count as valid, as long as in one of those rotations the string has the correct characters fixed at the correct positions. when you say If k is large then the O would have to be hiding a large constant for N to get below 23kn−f. - fyi k is currently a set of 32 'characters' (hell it could just be numbers from 1-32) from which the sequences of n length are being randomly generated $\endgroup$ – Matthew Prasinov Dec 11 '18 at 15:58
  • $\begingroup$ @MatthewPrasinov, that's not what I mean by periodic constraints. As an example of aperiodic constraints, consider $n=6$ with position 0 forced to colour 0 and position 3 forced to colour 1. Then a rotation by three can never meet the constraints. As an example of periodic constraints, consider $n=6$ with position 0 forced to colour 0 and position 3 forced to colour 0. Then a string which meets the constraints is guaranteed to always meet the constraints after a rotation by 3, so we have a correction factor. $\endgroup$ – Peter Taylor Dec 11 '18 at 16:01
  • $\begingroup$ ah, sorry for the confusion, i didnt explain properly perhaps. in my program, if n = 6 and position 0 is fixed to 0 and position 3 is fixed to 1, then all 6 rotations of that sequence are considered equivalent and subsequently ignored $\endgroup$ – Matthew Prasinov Dec 11 '18 at 16:03
  • 1
    $\begingroup$ Ahhhhh i get it now, sorry for my misunderstanding $\endgroup$ – Matthew Prasinov Dec 11 '18 at 16:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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