RichardKennaway comments on Rationalist horoscopes: A low-hanging utility generator. - Less Wrong

62 Post author: AdeleneDawner 22 May 2011 09:37AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (77)

Comments (77)

You are viewing a single comment's thread. Show more comments above.

Comment author: RichardKennaway 15 June 2011 10:14:47AM *  1 point [-]

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

Comment author: RichardKennaway 16 June 2011 03:04:26PM 2 points [-]

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

 8 16 19 18 5 2 15 33 28 1 25 24 26 31 32 10 4 27 20 7
3 16 23 6 33 17 22 13 21 12 14 30 9 19 29 8 11 2 5 18
15 28 25 4 24 26 1 10 32 31 27 3 20 7 16 33 23 19 17 6
13 8 22 21 12 14 30 29 9 25 15 5 2 11 18 28 26 24 32 4
27 1 20 10 3 31 33 23 7 16 17 19 13 29 6 8 14 24 22 21
Comment author: Will_Sawin 16 June 2011 03:15:25PM 0 points [-]

I second the claim that it works.

Powered by Reddit Powered by Reddit