Visiting N Rooms at Least Once

In a recent blog post, I described an algorithm that involved 10 rooms in a sultan’s harem. A mathematician had to visit each room. I wondered how many moves would be required, on average, for the mathematician to visit all 10 rooms if he used a random selection on each move.

Put another way, if you repeatedly select a random integer between 1 and 10, how many selections would you need to make on average, until you hit all 10 numbers at least once each? For example:

5 – 2 – 5 – 10 – 1 – 8 – 8 – 6 – 3 – 4 – 7 – 4 – 9

visits all ten rooms in 13 picks (or 12 moves if you don’t count the start).

I’m quite sure that there exists a clever solution to this problem that uses combinations and permutations. But the problem can also be tackled using brute force — just do a simulation program that keeps track of how many moves/selections are made until all 10 rooms are visited, and do this many times, and then take the average number of moves/selections.

To cut to the chase, I wrote a simulation. My simulation program ran 100,000 times and on average it took 29.25 moves to visit all 10 rooms at least once.

The moral of the story is that some problems are best solved analytically using mathematics, and some problems are best solved using a brute force simulation. When an elegant analytical technique is available, I prefer to use it. But for the visiting N rooms problem, a brute force approach was quick and effective.



Two random images from an Internet search for “brute force”. The movie makes sense but I don’t get the girl on the motorcycle.

Advertisements
This entry was posted in Miscellaneous. Bookmark the permalink.