Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\{1,2,\ldots,59\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences using every digit in the input string.
In the example above, a couple of possible sequences are: ${1,2,3,4,56,7,8}$ or ${1,2,3,45,6,7,8}$ which both satisfy lottery number conditions.
I thought of a combinatorial solution like this:
Let $n$ be the number of characters in the input string. If $n<7$ or $n>14$ then there is no solution possible. For valid input strings of length $n$, where $n\in [7,14]$, the problem reduces to the following:
In a string of length $n$ there are $n-1$ locations to put a comma. We have to put $6$ commas in $n - 1$ spaces such that no two consecutive spaces are empty (Otherwise, a number will be consist of three digits or be greater than $59$). This simply means arrange six ones like this:
111111
and then put $n-7$ $0$'s (representing emptiness) in the 7 slots. So, for example, if the input string is of length $8$ ("$12345678$") then we have to put $8-7 = 1$ zero in $7$ slots. So there are $7$ places where a zero can go and the strings generated are:
0111111, 1011111, 1101111, 1110111, 1111011, 1111101, 1111110
which correspond to $\{12,3,4,5,6,7,8\}$, $\{1,23,4,5,6,7,8\}$ etc.
So the problem reduces to computing $\binom{7}{k}$ and for each arrangement like above, put the corresponding commas in the appropriate place in the input string. So $0111111$ maps to $12,3,4,5,6,7,8$ (the space between 1 and 2 is left empty while the commans occupy the remaining 6 slots).
Is this algorithm a bad choice or can I do better?