Array rotation algorithm

Question

I'm developing an application which sends quotes to clients via email. Since quotes are obtained from various resources (per each client) they end up in a single array which is then used as a source for the email.

The desired functionality is that the client doesn't receive the same quote until the full rotation is complete, but there can be new quotes appearing in the array since I don't control that source.

E.g.

1. The client has an array of quotes [Foo, Bar, Baz].
2. Algorithm randomly picks Bar to be sent, flagging it as sent.
3. Next quote being sent is picking from [Foo, Baz].
4. Algorithm randomly picks Foo to be sent, flagging it as sent.
5. A new quote becomes available Qux.
6. Next quote being sent is picking from [Baz, Qux].
7. Algorithm randomly picks Baz to be sent, flagging it as sent.
8. Next quote being sent is picking from [Qux].
9. Algorithm picks Qux to be sent, flagging it as sent.
10. Next quote being sent has no available items and rerolls already sent items, picking again from [Foo, Bar, Baz, Qux].
11. Algorithm randomly picks Foo to be sent, flagging it as sent.

etc.

I can roughly imagine it being done like this, storing records of already SentQuote to the database and manually subtracting them from the array. In case there are zero matches I would reroll - invalidating the SentQuote.

This seems a bit cumbersome to me. Could there be a better way? I am using PHP 7.2

• Robert Harvey: Does your algorithm accurately describe the business requirements?
• Amit: Can't understand why bussines requirements are even needed for this question @RobertHarvey ? This is clearly a logical problem and OP has explained it perfectly.
• Robert Harvey: @AmitDwivedi: The 11-step "algorithm" that the OP provided clearly describes a business process. If that "algorithm" accurately reflects the business process it describes, then there's no possible way to simplify it (it being merely a reflection of the business process itself).
• Jan Richter: What is still a bit unclear to me: how do I reroll the SentQuote. I was thinking of having a table with quote.id, client.id, date_sent, exclude_rotation. Setting the exclude_rotation to 1 in case it is part of the active rotation, invalidating would mean to set exclude_rotation to 0 for the whole client. This would serve as a log of set quotes as well as an active rotation mechanism.
• amon: There isn't any better approach for these exact constraints. However, if you relax your constraints then more efficient solutions are possible. E.g. if new quotes don't become available before the list is exhausted you can enumerate all permutations and calculate the next index from the permutation number. Or if quotes may be repeated every k-th quote, then you can simply sample from all quotes at random and repeat while the sample is in the set of the last k quotes for that user.

Answer 1

You may want to base this on time, as opposed to whether it's been sent already or not as if the array swells quicker than you're sending them; some people may never get a quote sent and it'll never rotate.

You'll want to do something like this (if just PHP)

//$reset_time = <retrieve value of when you last cycled the list in epoch time, likely from database>
$clients = [
 [
 ["email"] => "[email protected]",
 ["lastemailsent"] => 0,
 ["pricedatawhateveretc"] => ...,
 ],
 [
 ["email"] => "[email protected]",
 ["lastemailsent"] => 1532965065,
 ["pricedatawhateveretc"] => ...,
 ],
];
function shouldSend($cl) {
 return $cl["lastemailsent"] < $reset_time;
}

This however means, you have to retrieve all the results from your database and iterate over them in PHP (very slowly)

If you're using (My)SQL, store reset_time in a table for "config", "settings" or "persistence", bonus points for doing something like this instead

$q = myAmazingQueryFunc("SELECT email, ... FROM prospective_clients WHERE LastEmailSent < :time OR LastEmailSent == 0", ["time" => $reset_time]);

You probably also want to add a LIMIT statement You can remove the LastEmailSent == NULL and use 0 instead of NULL. This way you can shorten the query to ..."WHERE LastEmailSent < :time"

You can also change it from random to using when they were last sent an email, so that people don't get hammered as frequently. With this method you can later change how your emails are sent out to add a time limit (so that someone doesn't get sent an email, you reset the system and they're unluckily the next random picked) as apposed to 1/0 "has an email been sent already" and resetting those all to zero

Consider whether PHP is the best language for this.

Oh, and whatever you do, ensure this has a one click button to unsubscribe/"stop sending me emails now".