A hobbyist programmer enquires...
** Situation: **
An iterator iterates over a range of big-numbers from 'min' to 'max'.
The current iteration's value is represented by a fixed-length array of 65535 values in the range of 0-255. (i.e. The array is always a 65535-digit base-256 number, with leading zeroes if required.)
Problem:
I want to include only the 'valid' values in the range, and skip over invalid values.
A value is valid if its base-256 representation contains at least one instance of every value in a given set of 'required values'.
a 'required value' is a value from 0-255
- the size of the set of required values is a power of 2, from 1-256
Question:
How can I determine up-front the total number of valid values contained within a range?
(Less-pressing) question:
Is there an elegant way of iterating over only the valid values, skipping value I know will be invalid?
Currently, I have to run through the array checking for the each required value at every iteration, and incrementing and re-checking if it's invalid.
But that method is no help in finding the total number of valid values, as the iteration position may be incremented by (rather large) arbitrary values, and the size of the range is far too large to check every value in it in this manner.
Thanks in advance for any assistance.
Lets start with a simplification, setting $\min=0, \max=256^{65535}-1$, which corresponds to taking all arrays of the sort you describe. You can compute how many have a particular set of $k$ values somewhere using the inclusion-exclusion principle. There are $256^{65535}$ total strings. There are $255^{65535}$ strings missing a particular value, because all the values have to come from the remaining $255$ choices. That would leave us with $256^{65535}-k255^{65535}$ that have all the $k$ values represented, except that we have subtracted twice the ones that are missing two different values, so we have to add them back in. For two specific values, there are $254^{655435}$ strings and there are $k \choose 2$ pairs of values to be missing, so we add in ${k \choose 2}254^{65535}$ We keep going, getting finally $$\sum_{i=0}^k(-1)^i{k \choose i}(256-i)^{65535}$$
To deal with $\min$ or $\max$ not being at the limit, we only need to deal with $\max$ being smaller. For higher $\min$, we can do the calculation over $[0,\max]$ and $[0,\min-1]$ and subtract. I would write a recursive function, which I will describe by example as if your arrays are base $10$ instead of $256$. Say you wanted numbers up to $456999$ that included $2$ and $7$. I would say that is the same as three times the numbers $00000-99999$ that include $2$ and $7$ plus those $00000-99999$ that include $7$ plus those $00000-56999$ that include $2$ and $7$. Basically take off the first digit, figure out what digits are still required, and call the routine with the smaller case.
To iterate over them I can only suggest starting with $\min$, counting by $1$'s and keeping the status updated as you carry. If you are looking for $2$ and $7$, when you get to $27000$ you know all the numbers will be acceptable for a while. That may be more bookkeeping than you want to do.