asked on
Design proper algorithm for lucky draw chances?
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.
ProgrammingDatabasesMiscellaneousMath / ScienceAlgorithms
Last Comment
Alan
ASKER
Yea, but in fact the number of chances in real scenario could be huge. And just in case anyone is curious, this is a legal lucky draw campaign for my client and I'm going to suggest my colleague a better approach, if there's any.
Thank you.
Thank you.
ASKER CERTIFIED SOLUTION
THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
Hi,
You 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.
You 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
ASKER
@Alan
@Sara
How do you declare the chance_array? and how do I set first_chance_index in cc?
In your code below:
Thank you.
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;
}
}
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
ASKER
Hi 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.
Do you have a simple sample in C# to illustrate your idea? Kinda difficult to get your idea in your last comment.
Thank you.
i am not a c# programmer but actually my last two posts cover all code parts you would need. so probably some basic coding mistakes in c# syntax from my side might puzzle you more than if you would put all code together i posted and try to make a little c# class yourself.
Sara
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
We seem to be straying from the actual question of an algorithm into programming?
Does the algorithm suggested above work? If not, please identify how it doesn't, and we can review.
Thanks,
lan.
Does the algorithm suggested above work? If not, please identify how it doesn't, and we can review.
Thanks,
lan.
ASKER
Hi Ian,
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.
Thank you.
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.
Hi,
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.
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.
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.