how to improve the efficient of program of crazy guy waiting airplane

Question

I recently wrote a program about the crazy guy waiting airplane question, which says:

A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the nth passenger in line has a ticket for the seat number n.) Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

I did monte carlo to get the answer, but not very efficient, since for the passengers, whose seat is sited. I first get a random number, and then checked from the first seat, if it is sited, then skip that one.

By the way the answer should be 1/2 :)

anybody has a better idea to do this one?

#include <iostream>
#include <vector>
#include <random>

using namespace std;

mt19937 generator;
uniform_real_distribution<double> ranuni(0, 1);

bool test(){
    vector<int> line(100, 0);

    int remaining(100);
    int temp = remaining * ranuni(generator);
    if (temp == 99)
    return 0;
    line[temp] = 1;
    --remaining; 

    for (int i = 1; i < 99; ++i){
        temp = remaining * ranuni(generator);

        auto itr = line.begin();
        while (temp != 0){
            ++itr;
            if (*itr == 0)
                --temp;
        }
        if (itr == line.end()-1)
            return 0;
        else
            *itr = 1;
        --remaining;
    }

    return 1;
}

int main(){
cout << "please input number of simulations" << endl;
int num;
cin >> num;

int sum(0);
for (int i = 0; i < num; ++i)
    sum += test();

cout << double(sum) / double(num) << endl;

return 0;
}

Answer 1

I'll offer a couple of thoughts. Probably not a definitive answer, though.

First, I wondered: if you pre-computed a "shuffled" list of plane seats to use, would that help things? The idea being: when a passenger attempts to sit in his/her seat and finds it occupied, you simply pop values off the list until you find one that is unoccupied instead of calling random(). You can pop them off because you don't want later passengers to waste time considering those (occupied) seats either. This means you DO avoid the problem near the end of the line where a random number generator keeps generating occupied seats. (Although, not yours I see, since you deterministically find an unoccupied seat when the assigned seat is occupied). Given such a shuffled list of seat assignments, it is very quick and easy to evaluate the original problem.

The real problem is that generating this "shuffled" list is exactly the same problem as the original one (for ticket# in 0..99, put ticket# in slot(random). Is it occupied? etc.) So, given that generating a nicely shuffled list of seat assignments has the same complexity as the original problem, is there a way we can simplify doing this lots and lots of times?

That brings me to my second thought: once you have one such shuffled list, there are lots of ways of creating other ones, much easier than 100 additional calls to random(). For example, just swap two of the values. The resulting list represents a different run of the problem with slightly different selections by passengers. Do this lots of times and you get many different runs.

The part I can't quite answer, though, is how to ensure the samples you get have a good sampling of the problem space (which is necessary for monte carlo to give you good results). I'll have to leave that for someone else.