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