# Thread: Lotto 6/49 program

1. ## Lotto 6/49 program

Hi I need some help for my program and I don't know how to start. I want to create a program which generates 6 numbers from a range of 1 to 49. How can you create that?
Also,is it possible to generate numbers which don't repeat?
All I know is that you have to use the rand() function:
Code:
`rand()%(49+1-1)+1`
I have found a code but unfortunately that is in c++
💯 Lottery 6/49 C++ | Code Playground
Is it possible to convert that code to C?

2. Originally Posted by wolly
Hi I need some help for my program and I don't know how to start. I want to create a program which generates 6 numbers from a range of 1 to 49. How can you create that?
Almost the same way you tried:
Code:
`n = (rand() % 49)+1;`
Taking the remainder of a division by 49 you'll get a value between 0 and 48 (inclusive), so you just need to add 1.
Originally Posted by wolly
Also,is it possible to generate numbers which don't repeat?
"Random" doesn't mean "don't repeat"... So, if you don't want repetition you must keep track of previously generated values.
Originally Posted by wolly
All I know is that you have to use the rand() function:
Code:
`rand()%(49+1-1)+1`
Which is the same as writing:
Code:
`rand() % 50`
and it is not what you wanted.
Originally Posted by wolly
I have found a code but unfortunately that is in c++
 Lottery 6/49 C++ | Code Playground
Is it possible to convert that code to C?
Yep, it is possible and simple to do... good luck!

3. Originally Posted by flp1969
Almost the same way you tried:
Code:
`n = (rand() % 49)+1;`
Taking the remainder of a division by 49 you'll get a value between 0 and 48 (inclusive), so you just need to add 1.

"Random" doesn't mean "don't repeat"... So, if you don't want repetition you must keep track of previously generated values.

Which is the same as writing:
Code:
`rand() % 50`
and it is not what you wanted.

Yep, it is possible and simple to do... good luck!
And some steps?
I found something like this,is this a good start?
''To pick lotto numbers, you make a pool (an array) of available numbers, pick one of them (an index) at random, and remove that number from the pool, by swapping it with the top one and then decreasing the number of items available. If you want a different selection each run, you call srand(time(NULL)) once at the start of the program. If you want to debug the same sequence, don't.''

4. That description sounds like the Fisher-Yates shuffling algorithm, except it "shuffles" only 6 numbers and leaves the rest in place.

So yes, it's a good start.

5. Originally Posted by wolly
And some steps?
I found something like this,is this a good start?
''To pick lotto numbers, you make a pool (an array) of available numbers, pick one of them (an index) at random, and remove that number from the pool, by swapping it with the top one and then decreasing the number of items available. If you want a different selection each run, you call srand(time(NULL)) once at the start of the program. If you want to debug the same sequence, don't.''
This is one way to do it, but since you need only 6 different values from 1 to 49, you can use a small array to "mark" those you already got and get another value if the corresponding index isn't 'marked'.

You can keep an array of 49 items:
Code:
`char marked[49] = { 0 };`
;
Every time you get a value you check if there is a mark:
Code:
```do {
n = rand() % 49;
} while ( marked[n] );
marked[n] = 1;
n++;```
For 6 out of 49 values, this doesn't seems problematic...

Of course, you'll have to create a better code.

6. Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_TO_PICK  6
#define HIGH_NUM    49

void generate_ticket(int *ticket) {
int used[HIGH_NUM + 1] = {0}; // initialized to all 0

for (int i = 0; i < NUM_TO_PICK; ++i) {
int r;
do
r = rand() % HIGH_NUM + 1;
while (used[r]);
used[r] = 1;
}

for (int i = 1, j = 0; i <= HIGH_NUM; ++i)
if (used[i])
ticket[j++] = i;
}

void display_ticket(int *ticket) {
for (int i = 0; i < NUM_TO_PICK; ++i)
printf("%2d ", ticket[i]);
putchar('\n');
}

int main() {
srand(time(NULL));

int ticket[NUM_TO_PICK];
generate_ticket(ticket);
display_ticket(ticket);

return 0;
}```

7. From john.c code I would change just a little thing:
Code:
```void generate_ticket( int *ticket )
{
int used[HIGH_NUM + 1] = {0}; // initialized to all 0

for ( int i = 0; i < NUM_TO_PICK; ++i )
{
int r;

do
// NOTICE this is the same as 'r = (rand() % HIGH_NUM) + 1;'
// because % has precedence.
r = rand() % HIGH_NUM + 1;
while ( used[r] );

// Here we already know r isn't used! We don't need the third loop.
ticket[i] = r;

used[r] = 1; // mark as used!
}
}```

8. The reason I didn't do it that way is to get the values in sorted order. I would change one thing in my original code, though, which is to use position 0 in the used array.
Code:
```void generate_ticket(int *ticket) {
int used[HIGH_NUM] = {0}; // initialized to all 0

for (int i = 0; i < NUM_TO_PICK; ++i) {
int r;
do
r = rand() % HIGH_NUM;
while (used[r]);
used[r] = 1;
}

for (int i = 0, j = 0; i < HIGH_NUM; ++i)
if (used[i])
ticket[j++] = i + 1;
}```

9. Originally Posted by john.c
The reason I didn't do it that way is to get the values in sorted order
Ahhhh... good one! I was really thinking 'john.c wouldn't miss this... why this thrid loop?!'... I didn't thought about sorted order!

10. My take at it:

Code:
```void pick_n(int n, int out[])
{
int pool[POOL_SIZE];
for (int i = 0; i < POOL_SIZE; ++i) {
pool[i] = i + 1;
}
int top = POOL_SIZE;
for (int i = 0; i < n; ++i) {
int j = rand() % top--;
out[i] = pool[j], pool[j] = pool[top], pool[top] = out[i];
}
}```

11. Originally Posted by john.c
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_TO_PICK  6
#define HIGH_NUM    49

void generate_ticket(int *ticket) {
int used[HIGH_NUM + 1] = {0}; // initialized to all 0```
When you placed High NUM 49 and you added one did you used 0 as a first number?
I thought 0 is a number that is not played in this game but I'm not sure.

12. Originally Posted by wolly
When you placed High NUM 49 and you added one did you used 0 as a first number?
I thought 0 is a number that is not played in this game but I'm not sure.
john.c already explained this, below... in the first version of this routine the 'used' array was declared with 50 elements because he wasn't using used[0].

So you can see a similar approach, but not using arrays, and I believe it is a tiny little bit faster, here's another approach:
Code:
```void generate_ticket( int *ticket )
{
int count, r;
unsigned long long used = 0, mask;

count = NUM_TO_PICK;
while ( count-- )
{
do
{
r = rand() % HIGH_NUM;
mask = 1ULL << r;
} while ( used & mask );

used |= mask;
}

r = 0;
count = NUM_TO_PICK;
do
{
mask = 1ULL << r++;

if ( used & mask )
{
*ticket++ = r;
count--;
}
} while ( count );
}```
Less space occupied on stack, no need to zero all the array... but, essentially, this is the same as john.c code (just more complex).
PS: I didn't test the code yet...

13. Using a bitmap is a pretty good idea. You could store the numbers that way without converting to an int array. Then it's easy to compare to the drawn number to count matches.

I set the code for 10/64 instead of 6/49 for the example.
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef unsigned long long ULL;

#define MAX_HIGH_NUM ((int)sizeof(ULL) * 8) // at least 64
#define HIGH_NUM     64
#define TICKET_SIZE  10
#define NUM_TICKETS  20

ULL generate_ticket(int size) {
ULL ticket = 0;
for (int count = size; count--; ) {
ULL mask;
do
mask = 1ULL << (rand() % HIGH_NUM);
while (ticket & mask);
ticket |= mask;
}
return ticket;
}

void print_ticket(ULL ticket) {
for (int i = 0; i < MAX_HIGH_NUM; ++i)
if (ticket & (1ULL << i))
printf("%2d ", i + 1);
putchar('\n');
}

void print_highlighted_matches(ULL ticket, ULL draw) {
ULL matches = ticket & draw;
int cnt = 0;
for (int i = 0; i < MAX_HIGH_NUM; ++i) {
ULL mask = 1ULL << i;
if (ticket & mask) {
if (matches & mask) {
printf("\033[1;36m");
++cnt;
}
printf("%2d ", i + 1);
if (matches & mask)
printf("\033[0;0m");
}
}
printf("  [ %d ]\n", cnt);
}

int main() {
srand(time(NULL));

ULL tickets[NUM_TICKETS];
for (int i = 0; i < NUM_TICKETS; ++i)
tickets[i] = generate_ticket(TICKET_SIZE);

ULL draw = generate_ticket(TICKET_SIZE);
printf("Draw:\n");
print_ticket(draw);
putchar('\n');

printf("Tickets:\n");
for (int i = 0; i < NUM_TICKETS; ++i)
print_highlighted_matches(tickets[i], draw);

return 0;
}```
Example output (using bbcode tags instead of colors) :
Code:
```Draw:
4  6 15 20 24 29 35 36 48 62

Tickets:
10 12 15 22 24 31 43 48 61 62   [ 4 ]
5  6 12 22 31 35 44 55 58 64   [ 2 ]
23 27 29 34 37 42 48 50 53 54   [ 2 ]
11 12 20 28 33 34 45 52 56 59   [ 1 ]
1 10 24 26 29 34 44 51 63 64   [ 2 ]
6 13 15 22 27 38 40 49 58 60   [ 2 ]
4  7  9 11 23 39 51 57 60 62   [ 2 ]
4  5  6 21 38 39 43 48 52 64   [ 3 ]
25 30 36 37 38 40 45 55 60 63   [ 1 ]
8 14 26 30 31 33 40 41 43 63   [ 0 ]
3 25 34 35 38 45 47 51 52 59   [ 1 ]
5 15 17 19 25 29 42 48 50 51   [ 3 ]
7 17 18 24 29 33 37 46 47 58   [ 2 ]
3  6  8 18 20 34 45 47 53 64   [ 2 ]
13 15 17 18 19 34 35 55 61 63   [ 2 ]
14 16 21 22 28 30 36 53 54 59   [ 1 ]
2  5  6  7  8 12 24 46 51 55   [ 2 ]
2  6 10 15 28 41 53 55 62 64   [ 3 ]
8 15 19 21 27 37 43 48 49 64   [ 2 ]
9 12 16 25 35 46 48 49 56 62   [ 3 ]```

14. Here's the excellent code from john.c, but using the parameters for the problem (tickets with 6 numbers from 1 to 49) and a "trully random number generator", if your processor is Intel or AMD and supports it:

Code:
```// tickets.c
//
//   Compile with:
//      cc -O2 -march=native -o tickets tickets.c
//
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

// This will work for GCC and Intel/AMD processors only.
#if defined(__x86_64) || defined(__i386)
#ifdef __GNUC__
#include <immintrin.h>
#endif

// immintrin.h defines __RDRND__ if the target processor supports it.
#ifdef __RDRND__
// Need __cpuid() in main().
#include <cpuid.h>

static unsigned int RAND_( void )
{
unsigned int r;

while ( ! _rdrand32_step( &r ) );

return r;
}

static void do_nothing(void) {}
#endif
#endif

static void SRAND_(void) { srand(time(NULL)); }

static unsigned int (*RAND)(void) = (unsigned int (*)(void))rand;
static void (*SRAND)(void) = SRAND_;

// HIGH_NUM cannot exceed 63!
#define HIGH_NUM     49
#define TICKET_SIZE  6
#define NUM_TICKETS  20

uint64_t generate_ticket( unsigned int count )
{
uint64_t mask, ticket = 0;

while ( count-- )
{
do
mask = 1ULL << ( RAND() % HIGH_NUM );
while ( ticket & mask );

ticket |= mask;
}

return ticket;
}

void print_ticket( uint64_t ticket )
{
unsigned int count, i;

for ( i = 0, count = HIGH_NUM; count--; i++ )
if ( ticket & ( 1ULL << i ) )
printf( "%2u ", i + 1 );
putchar( '\n' );
}

void print_highlighted_matches( uint64_t ticket, uint64_t draw )
{
uint64_t mask, matches = ticket & draw;
unsigned int i, cnt = 0;

for ( i = 0; i < HIGH_NUM; ++i )
{
mask = 1ULL << i;

if ( ticket & mask )
{
if ( matches & mask )
{
printf( "\033[1;36m" );
++cnt;
}

printf( "%2u ", i + 1 );

if ( matches & mask )
printf( "\033[m" );
}
}

printf( "  [ %u ]\n", cnt );
}

int main( void )
{
unsigned int i;
uint64_t draw, tickets[NUM_TICKETS];

// Test if your processor supports RDRAND only
// if __RDRND__ is defined.
#ifdef __RDRND__
int a, b, c, d;

__cpuid( 1, a, b, c, d );
if ( c & bit_RDRND )
{
RAND = RAND_;
SRAND = do_nothing;
}
#endif

SRAND();

for ( i = 0; i < NUM_TICKETS; ++i )
tickets[i] = generate_ticket( TICKET_SIZE );

draw = generate_ticket( TICKET_SIZE );
printf( "Draw:\n" );
print_ticket( draw );
putchar( '\n' );

printf( "Tickets:\n" );

for ( i = 0; i < NUM_TICKETS; ++i )
print_highlighted_matches( tickets[i], draw );

return 0;
}```

15. Just to be compliant with Intel recomendations, the RAND_() function should be like this:
Code:
```  static unsigned int RAND_( void )
{
unsigned int r;
int retries;

// Intel recomends reading 10 times, in case of failure...
retries = 10;
while ( retries-- )
if ( _rdrand32_step( &r ) )
return r;

fputs( "\e[1;31mERROR\e[m: RDRAND failure!\n", stderr );
exit(EXIT_FAILURE);
}```
But, in my experience, RDRAND instruction never fails more than once... if it fails ever...

Popular pages Recent additions