2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Welcome to CS.SE! The lack of helpful formatting makes your post harder to comprehend. I encourage you to take some time to improve the presentation; we collected some advice here. It would also help to break your post into multiple paragraphs. Finally, how would you like to measure "better"? "Better", in what respect? Running time? Ease of implementation? Something else? Thank you! $\endgroup$ – D.W.♦ Mar 28 '17 at 23:13
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ No, the solution if it exists will always be a set of 7 numbers (where each number is between 1 and 59 inclusive). For 12345678, {1,2,3,4,5,6,78} is invalid (since 78 > 59) but {1,2,3,4,56,7,8} is valid. $\endgroup$ – user3079275 Mar 28 '17 at 22:46
  • $\begingroup$ I mean the 78 one is rejected - I should have been more clear. The alorithm will loop over all the possible solutions and reject any with numbers that are invalid. $\endgroup$ – user3079275 Mar 28 '17 at 22:49
  • $\begingroup$ In other words, you first generate all the combinations and then sweep to remove bad pairs. But another thing is it doesn't include {12,34,56,7,8} in your description and your example. $\endgroup$ – Iraj Hedayati Mar 28 '17 at 23:39
  • $\begingroup$ {12,34,56,7,8} is not valid.. because there need to be 7 numbers in the set $\endgroup$ – user3079275 Mar 29 '17 at 6:23
  • 1
    $\begingroup$ I edited my answer. I suggest you do the same. Because yours is also correct. I would conclude that: your algorithm is simpler but it will generate all the valid combinations that require another round. But, as the numbers are very small in this case (7 to 35), I don't think that would be a problem. $\endgroup$ – Iraj Hedayati Mar 29 '17 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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