Algorithm to identify if a string of numbers is a lottery sequence

Question

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?

Answer 1

I'm not sure if I understood your solution or not. But it seems that 78 also is included in the last sequence.

Here is my answer: For any valid sequence $w$ ($w$ is valid iff $7\le n\le14$ where $n$ is the size of $w$) there should be $n-7$ pairs and $14-n$ single numbers ($14-n+n-7=7)$. We run a recursive function:

1. Setup the memory: $A$ count of pairs and $B$ count of single numbers in the sequence

2. If $w[0]$ is equal or less than 5, then there are two possibilities:

   1. It can be a single member if $B<14-n$
   2. It can be combined with the next number if $A<n-7$

   If neither of these cases is valid, this sequence is not valid

3. If $w[0]$ is greater than 5, then it can not be combined with the next number. If $A\ge n-7$ then this sequence is not valid.

Then run the same algorithm for the sequence following $w[0]$ (or $w[1]$ for case 1.1).

For example $w=12345678$

1. $\{1\}$ and $\{12\}$
2. $\{1,2\}$, $\{1,23\}$, $\{12,3\}$
3. $\{1,2,3\}$, $\{1,2,34\}$,$\{1,23,4\}$, $\{12,3,4\}$
4. $\{1,2,3,4\}$, $\{1,2,3,45\}$, $\{1,2,34,5\}$, $\{1,23,4,5\}$, $\{12,3,4,5\}$
5. $\{1,2,3,4,5\}$,$\{1,2,3,4,56\}$,$\{1,2,3,45,6\}$,$\{1,2,34,5,6\}$,$\{1,23,4,5,6\}$,$\{12,3,4,5,6\}$
6. $\{1,2,3,4,5,6\}$,$\{1,2,3,4,5,67\}$,$\{1,2,3,4,56,7\}$,$\{1,2,3,45,6,7\}$,$\{1,2,34,5,6,7\}$,$\{1,23,4,5,6,7\}$,$\{12,3,4,5,6,7\}$
7. $\{1,2,3,4,5,6,7\}$,$\{1,2,3,4,5,67,8\}$,$\{1,2,3,4,56,7,8\}$,$\{1,2,3,45,6,7,8\}$,$\{1,2,34,5,6,7,8\}$,$\{1,23,4,5,6,7,8\}$,$\{12,3,4,5,6,7,8\}$

all the sequences ended with $8$ are valid.