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.
trowaAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
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.

AlanConsultantCommented:
Hi Trowa,

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.
0
trowaAuthor Commented:
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.
0
sarabandeCommented:
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];

Open in new window


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
0

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 trial
Big Business Goals? Which KPIs Will Help You

The most successful MSPs rely on metrics – known as key performance indicators (KPIs) – for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

AlanConsultantCommented:
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.
0
sarabandeCommented:
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;
};

Open in new window


- 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;
       }
}

Open in new window


- 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;
}

Open in new window


Sara
0
trowaAuthor Commented:
@Alan

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;
       }
}

Open in new window

Will I get number_chances = 0 for first customer?

Thank you.
0
sarabandeCommented:
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;

Open in new window


in c# it would be (likely)

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

Open in new window


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 };

Open in new window


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
0
trowaAuthor Commented:
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.
0
sarabandeCommented:
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.

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
0
AlanConsultantCommented:
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.
0
trowaAuthor Commented:
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.

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

Thank you.
0
AlanConsultantCommented:
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.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Programming

From novice to tech pro — start learning today.