You are here

Recreation

Things to do for fun.

Random non-repeating sequences

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…

Group/Project: 

I'm done with The Onion

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…

Group/Project: 

Won a poker tournament yesterday

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…

Group/Project: 

ANSWERS: Antonyms

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

Group/Project: 

Antonyms: a little word puzzle

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…

Group/Project: 

Rolling 18

I was playing in a D&D game with my boy last Sunday, and someone brought up the question of how likely a character was to have an 18 stat. Of course the rest of the session was a loss for me, as I sat there trying to do the math with pencil, paper, and a four-function calculator.

D&D has six stats, each a number between 3 and 18. The character roll-up rules we are playing specify that each stat will be obtained by rolling four dice and taking the top three.

About 9% of D&D characters will have an 18 stat. The answer is explained here. Fob

Group/Project: 

ANSWER: Rolling 18

So as I said, we're rolling six stats for D&D, where each stat is determined by rolling four six-sided dice and taking the top three…

Group/Project: 

Review: Swindle

It seems like I've been posting a lot of negative stuff lately. I'm a naturally cranky, opinionated person, but there's lots of things I enjoy. I should report on them too.

I recently reviewed the worst juvie novel I've ever read—the "banned book" The Transall Saga. Today I have the happier task of reviewing a well-written and intriguing novel intended for a slightly younger age group. Gordon Korman's Swindle came to my attention today when my son brought it home from the school Book Fair, where apparently every kid in school bought a copy. I'm always suspicious of these sudden hits, but I read a couple of chapters of Swindle this morning.

I'm hooked…

Group/Project: 

Royal Flush #1

My friend Burt hits a royal flush at our weekly poker game January 15, 2008

Taxonomy upgrade extras: 

Terminator: The Sarah Connor Chronicles

This is a review of the first few minutes of the first episode of Terminator: The Sarah Connor Chronicles. It contains a spoiler—indeed, it spoiled the whole series for me—so please don't read beyond the break if you want to keep some badly-written TV SF fun until you see it for yourself…

Group/Project: 

Pages

Subscribe to RSS - Recreation