4 ms·
I'm sorry, this seems incredibly naive, but couldn't you just have cards = range(52) shuffled = [] while len(cards)>0: shuffled.append(rand
by eximius 11y ago
I'm sorry, this seems incredibly naive, but couldn't you just have
cards = range(52)
shuffled = []
while len(cards)>0:
shuffled.append(random.choice(cards))
cards.remove(shuffled[-1])
return shuffled
which should be, given a good randomness, literally equivalent to drawing randomly from a pool of 52 cards to form a deck. Is this somehow less efficient than their algorithm?
- rav 11y agoThat is essentially the same as the algorithm in the article, which was Figure 3: for (i is 1 to 52) Swap i with random position between i and 52 After i iterations, the first i entries are your "shuffled", and the last 52 - i entries are your "cards". "random.choice(cards)" corresponds to picking a "random position between i and 52".
- lmm 11y agoBut they didn't do that - they picked a random position between 1 (not i) and 52 each time, which gives a biased shuffle. Even if their randomness had been perfect, this would have been problematic.
- eximius 11y agoI suppose. I guess I just prefer the more direct, naive algorithm when the performance gain would seem to be so small. (not that I've profiled it or anything :/)
- rav 11y agoFrom a CS theory perspective, I would say it's two implementations of the same algorithm, or two ways of phrasing the same algorithm. The most natural formulation in your eyes is probably not the same as the most natural formulation in the eyes of the article author.
- solutionyogi 11y agoI think the problem is the randomness. When you use your language's random function, you are getting a pseudorandom generator. As noted in the article, they were able to figure out the seed for the random function. Once you know the seed, the game is over. The adversary can now figure out the exact shuffled deck. Also see: http://ericlippert.com/2013/05/06/producing-permutations-part-seven/ http://ericlippert.com/2013/05/06/producing-permutations-par...
- eximius 11y agoMy point was the algorithm, not the implementation, hence my disclaimer on 'good randomness'.
- astrodust 11y agoThe algorithm is not the problem. The "good randomness" part is the entire problem. Easy way to shuffle a deck is just to give each card a random 32-bit index and sort. You don't need to do anything fancy to get them shuffled up. The problem is, if your random number generator is predictable then the algorithm doesn't matter.
- AndrewStephens 11y agoEven that is very slightly biased, since you don't specify what happens when 2 cards accidentally end up with the same index. It's better to do the shuffle described in the document. It is not just the predictability of the generator that is the issue (all PRNG are predictable really), what really matters is the size of the seed state, which should vastly exceed the number of value shuffles (52! - a huge number).
- neckro23 11y agoIt's not mentioned by name in the article, but the "proper" way to do it is with a Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Depending on the array implentation, adding and removing elements is often an O(n) operation, which isn't terribly efficient. The Fisher-Yates method lets you get the same results without messing with the array length.
- ecdavis 11y agoSince we're posting Python snippets: cards = range(52) random.shuffle(cards) return cards