The IT Service Excellence Tool Kit has best practices to keep your clients happy and business booming. Inside, you’ll find everything you need to increase client satisfaction and retention, become more competitive, and increase your overall success.

This could be an easy question and in fact, this is simple. But just wondering what's the proper algorithm for lucky draw chances?

Let's say in every new deposit amount of X get a no of chances of Y. Providing X = $1000, Y = 1

If there's a customer A credited $10000, he got 10 chances in this month.

If there's a customer B credited $2000, he got 2 chances in this month.

If there's a customer C credited $100, he got 0 chances in this month.

If there's a customer D credited $3500, he got 3 chances in this month.

By end of this month, how do I use a proper algorithm to pick a lucky draw winner? That's to pick a winner among this 15 chances.

One of the approaches is to create multiple chances in a temp table, and then random a position to pick the winner. But my question is what if the total no of chances is a very big number? Will the process of populating this temp table become slow?

Thank you.

Let's say in every new deposit amount of X get a no of chances of Y. Providing X = $1000, Y = 1

If there's a customer A credited $10000, he got 10 chances in this month.

If there's a customer B credited $2000, he got 2 chances in this month.

If there's a customer C credited $100, he got 0 chances in this month.

If there's a customer D credited $3500, he got 3 chances in this month.

By end of this month, how do I use a proper algorithm to pick a lucky draw winner? That's to pick a winner among this 15 chances.

One of the approaches is to create multiple chances in a temp table, and then random a position to pick the winner. But my question is what if the total no of chances is a very big number? Will the process of populating this temp table become slow?

Thank you.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Thank you.

One of the approaches is to create multiple chances in a temp table, and then random a position to pick the winner. But my question is what if the total no of chances is a very big number? Will the process of populating this temp table become slow?

if you use a simple dynamic array and push the customer id to that array for each chance, the lucky draw simply would do

```
int lucky_draw = random(number) modulo chance_array.number_of_elements();
Customer winner = chance_array[lucky_draw];
```

the only drawback of this approach is the storage you need for the array of chances. the winner is evaluated in o(1).

to avoid that the dynamic array would grow one by one (what is slow and would create memory wholes) you should grow the array in big chunks (normally you can do so by calling a reserve member function).

Sara

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialYou say it could be huge, but how huge?

For example an array of a few million entries would not actually take up much space.

Alan.

the number of chances in real scenario could be huge

- build a structure with customer id, number of chances, and cumulated offset of chances already stored,

```
struct CustomerChance
{
string customer_id;
int chances;
int first_chance_index;
};
```

- create an array of that structure which size is all customers that have at least 1 chance and fill the array sequentially.

```
int number_chances = 0;
foreach (customer in customers)
{
if (customer.credit >= 1000)
{
int current_chances = (int)(customer.credit/1000.);
CustomerChance cc = { customer.id, current_chances, number_chances };
array_chances.push_back(cc);
number_chances += current_chances;
}
}
```

- if you want to find the lucky_draw you do

```
int lucky_draw = random(number) modulo number_chances;
int begin = 0;
int end = array_chances.number_of_elements();
int middle = (begin + end)/2;
string winner;
while (begin < end)
{
CustomerChance cc = chance_array[middle];
if (cc.first_chance_index > lucky_draw)
{
// the lucky draw is below the current customer range of chances
end = cc.first_chance_index - 1;
}
else if (cc.first_chance_index + cc.chances) <= lucky_draw)
{
// the lucky draw is after the current customer range of chances
begin = cc.first_chance_index + cc.chances;
}
else
{
// we found the winner
winner = cc.customer_id;
break;
}
middle = (begin + end)/2;
}
```

Sara

You say it could be huge, but how huge?Yup, it could be in few millions.

@Sara

How do you declare the chance_array? and how do I set first_chance_index in cc?

In your code below:

```
int number_chances = 0;
foreach (customer in customers)
{
if (customer.credit >= 1000)
{
int current_chances = (int)(customer.credit/1000.);
CustomerChance cc = { customer.id, current_chances, number_chances };
array_chances.push_back(cc);
number_chances += current_chances;
}
}
```

Will I get number_chances = 0 for first customer?Thank you.

How do you declare the chance_array?

this depends on the programming language you are working with.

in c++ it would be

```
std::vector<CustomerChance> array_chances;
```

in c# it would be (likely)

```
List<CustomerChance> array_chances = new List<CustomerChance>();
```

in any case it is an array where each customer with a credit >= 1000 would be added with the number of chances and with an offset that tells how many chances already have been counted for all the customers which are already stored in the array.

so for your initial sample

If there's a customer A credited $10000, he got 10 chances in this month.

If there's a customer B credited $2000, he got 2 chances in this month.

If there's a customer C credited $100, he got 0 chances in this month.

If there's a customer D credited $3500, he got 3 chances in this month.

you would get

```
array_chances[0] = { "A", 10, 0 };
array_chances[1] = { "B", 2, 10 };
array_chances[2] = { "D", 3, 12 };
```

you see that 'first_chance_index' was set to the cumulated chances of all customers before (A has no chances before, B has 10 chances of A before, D has 12 chances of A and B before). taht way we don't need an array with all chances { A, A, A, A, A, A, A, A, A, A, B, B, D, D, D, ... } but only 1 per customer with the same information.

Sara

Do you have a simple sample in C# to illustrate your idea? Kinda difficult to get your idea in your last comment.

Thank you.

Kinda difficult to get your idea in your last comment.if you would say what part is difficult to understand, i probably could help.

Sara

Does the algorithm suggested above work? If not, please identify how it doesn't, and we can review.

Thanks,

lan.

I'm actually looking if there's any published paper/ article talking about the lucky draw algorithm, if there's any.

I just want to know how to actually built the process and suggest to my colleague.

Does the algorithm suggested above work?which comments or points are you referring to?

Thank you.

Any of them.

Probably best to tie down the algorithm first, then move on to how to actually build it, since the latter will be language specific.

Thanks,

Alan.

Programming

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

In terms of an algorithm, I would be inclined to model 'raffle tickets':

Customer A gets tickets 1 to 10 inclusive

Customer B gets tickets 1 to 12 inclusive

Customer C gets no tickets

Customer D gets tickets 13 to 15 inclusive

I would then generate a random integer from 1 to 15 inclusive, and determine the winner from that.

Generating the table of tickets would be done throughout the month (or whatever period each 'draw' is over), so no noticeable load as you go, and the output is nothing more than a table of numbers and the name of the 'holder' of that ticket, which is appended to after each transaction is processed so very small.

After you have the winning number, you lookup that number in the table, and get the winner - no significant load there either.

Alan.