Jump to content
  • Advertisement
Sign in to follow this  
dacosi

Probability Tree Implementation?

This topic is 4163 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is a C++ problem: Suppose there is an array of integers from 1 to 52 inclusive. Write a function that reorder this array in a random manner. This function should print out each possible order with equal probability. ( The question strongly suggested that rand() should be used ) I managed to reorder the array in a random order. But, I could not quite get the part where it says equal probability. Is it to print each possible outcome once? Should I print out all the permutations of the order in random order by implementing a probability tree ,store it and print it in random order? But this will mean 52! results to store. ( Not too encouraging ) Or should I just iterate 52! times to get the results but that will mean possible duplicates which defies "each possible outcome"? Sorry for this question sounds dumb but I have been pondering on it for quite a few days. I think it is really a question of interpretation.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by dacosi
Is it to print each possible outcome once?

Should I print out all the permutations of the order in random order by implementing a probability tree ,store it and print it in random order? But this will mean 52! results to store. ( Not too encouraging )

Or should I just iterate 52! times to get the results but that will mean possible duplicates which defies "each possible outcome"?

Sorry for this question sounds dumb but I have been pondering on it for quite a few days. I think it is really a question of interpretation.


None of those are correct.

What "with equal probability" means is without bias. Any given ordering should be just as likely to occur as any other one. That doesn't mean that you need to do 52! trials and expect to get each ordering once - in fact, you would be very, very likely to have written it incorrectly if you got each ordering once!

Consider a simpler example: a coin. Whenever you flip a coin, it comes up either heads or tails, with equal probability. That is, the probability of each (and we are going to ignore the tiny chance of it landing on its edge, or any consideration of bias in the coin) is 1/2. If you flip the coin twice, well, it *might* come up heads once and tails once, but coming up the same both times is also quite valid. Two runs is not that big of a test.

So, now, imagine a fair die with 52! sides, each of which corresponds to a possible ordering of the numbers. If you could roll this die and report the corresponding ordering, then you would have a valid solution to the problem.

They don't want you to do 52! trials (it would take far, far more time than the universe is expected to last). They want you to do one trial, but they want you to be able to show that it is a *fair* trial.

There are many ways to get this wrong while thinking you are getting it right. There are at least two things to consider:

1) rand(), normally, isn't as random as it really needs to be for this to work: because every random 32-bit number simply depends on the previous random 32-bit number (in *typical* implementations), only 2^32 of the orderings can possibly come up. This is a tiny, tiny fraction of 52!. Nevertheless, we usually ignore this kind of issue, at least in games programming, because the set of 2^32 orderings that might come up will probably make a fair sampling.

2) If you do the shuffling by iteratively swapping elements, you actually need to be careful about your swapping policy, or you will introduce a definite bias. See here for more.

Of course, in C++, you actually *shouldn't* write this function, because it basically already exists.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!