I think 2 and 3 are mutually exclusive − 3 is a pretty strict specification of how an item is chosen, and doesn’t lend itself to making 2 guaranteed to happen at all.
(3) only says what you know about the next one, given the last P-1. The actual algorithm can know the entire previous history. So if object X has just been passed over Q-1 times, it must be chosen next by (2), but that doesn’t violate (3), because that information isn’t available from the last P-1 drawings.
ETA: A simple algorithm that I think works is this:
1. Generate the first P-1 items at random, all distinct. At each subsequent step: 2. If there is an item that has not appeared in the last Q-1 drawings, choose it. 3. Otherwise, choose uniformly from among those that have not appeared in the last P-1 drawings.
This isn’t the only possible algorithm. Instead of a uniform distribution in part (3), one might weight it towards those that were last chosen longer ago, with (2) being a special case of that.
I couldn’t resist programming it. I have a MATLAB function randchoiceseq(N,P,Q,K), where N, P, and Q are as above and K is the length of sequence to generate. If it would be useful for the horoscope site, I can send a copy. Result of randchoiceseq(33,16,40,100):
This suggests an exercise in mathematics and programming:
Given a set of N objects, generate an indefinitely long sequence of random members of the set, such that:
No object is drawn more than once in any consecutive P drawings, for a given P ⇐ N.
Every object is drawn at least once in every consecutive Q drawings, for a given Q >= N.
The probability distribution of the next drawing, given only knowledge of the last P-1 drawings, is uniform over the remaining N-P+1 objects.
I think 2 and 3 are mutually exclusive − 3 is a pretty strict specification of how an item is chosen, and doesn’t lend itself to making 2 guaranteed to happen at all.
(3) only says what you know about the next one, given the last P-1. The actual algorithm can know the entire previous history. So if object X has just been passed over Q-1 times, it must be chosen next by (2), but that doesn’t violate (3), because that information isn’t available from the last P-1 drawings.
ETA: A simple algorithm that I think works is this:
1. Generate the first P-1 items at random, all distinct.
At each subsequent step:
2. If there is an item that has not appeared in the last Q-1 drawings, choose it.
3. Otherwise, choose uniformly from among those that have not appeared in the last P-1 drawings.
This isn’t the only possible algorithm. Instead of a uniform distribution in part (3), one might weight it towards those that were last chosen longer ago, with (2) being a special case of that.
I couldn’t resist programming it. I have a MATLAB function randchoiceseq(N,P,Q,K), where N, P, and Q are as above and K is the length of sequence to generate. If it would be useful for the horoscope site, I can send a copy. Result of randchoiceseq(33,16,40,100):
I second the claim that it works.