FOB

While doing some research for an upcoming paper, I came upon a 2008 blog post describing a special case of the following interesting problem:

Given an alphabet of n symbols, construct a uniformly-selected sequence of m of these symbols, with the sequence containing no duplicate symbols.

[Updated 2009/12/14] The difficulty arises when both m and n are large. The obvious method is a rejection method: repeatedly pick a random symbol from the alphabet and check whether you've picked it already. If not, append it to your target number. The problem is that the duplicate check seems to require log m time even if you code it cleverly, giving an asymptotic performance of O(m log m). Hash tables can help some, but ultimately you're going to waste a lot of time checking for the unlikely case that you've generated a duplicate.

There were various solutions given in the comments, but none of them were optimal. A spoiler follows…

I've been a huge fan of The Onion, the satirical newspaper originally published by the University of Wisconsin, for about 15 years now. I've purchased their books and audiobooks, downloaded their videocasts to my TiVO, etc.

That ended tonight…

I won a poker tournament last night. It wasn't a big tournament: 20 people playing at an American Legion Hall in North Portland, with the rake mostly going to charity. $20 buy-in, with payouts of $225/$125/$75. By the time I bought a round of drinks and threw in some charity money, I came home with about $150…

Here's the answers to antonyms:

1. antonym :: synonym
2. arcane :: mundane
3. aristocratic :: plebian
4. coerce :: entreat
5. embrace :: abjure
6. exacerbate :: ameliorate
7. exotic :: quotidian
8. sostenuto :: staccato
9. reduce :: oxidize
10. materialize :: dematerialize

Explanations available on request.

I keep wanting to blog about my latest tiny piece of software, but I keep having one more bug or feature.

So instead, I've cooked up this little word game. Tell me what you think of it…