Design proper algorithm for lucky draw chances?

trowa
trowa used Ask the Experts™
on
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.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
AlanConsultant

Commented:
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.

Author

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.
Top Expert 2016
Commented:
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
Success in ‘20 With a Profitable Pricing Strategy

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden using our free interactive tool and use it to determine the right price for your IT services. Start calculating Now!

AlanConsultant

Commented:
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.
Top Expert 2016

Commented:
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

Author

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.
Top Expert 2016

Commented:
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

Author

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.
Top Expert 2016

Commented:
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
AlanConsultant

Commented:
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.

Author

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

Commented:
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.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial