Perfect card shuffling - PrismoSkills
Puzzle: Given a perfect random number generator, write a function to generate a perfect shuffle of cards in 52 iterations only.Shuffle is perfect if every card is equally random as any other card i.e. the probability of choosing every card is same.
Solution: If there is a perfect random number generator, then 52*random() would give a number with equal
probability every time. So we can rest assured on the randomness. However, if we just use 52*random() to get every
card in the deck, then it cannot be done in 52 iterations due to collisions.
To do it in 52 iterations itself, swap the card chosen with the newBeginning of the array and
multiply the next random() call with the reduced size of the array (52 - newBeginning)
This way, the randomness of the cards will be preserved and the deck will be shuffled in 52 iterations only.
Read full article from Perfect card shuffling - PrismoSkills
No comments:
Post a Comment