StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Something that might be faster than shuffling the whole array:</p> <pre><code>java.util.Random r = new java.util.Random(); int c1 = r.nextInt(52), c2 = r.nextInt(51), c3 = r.nextInt(50); if(c2 >= c1) c2++; if(c3 >= Math.min(c1, c2)) c3++; if(c3 >= Math.max(c1, c2)) c3++; System.out.println("Card 1: " + rank[c1]); System.out.println("Card 2: " + rank[c2]); System.out.println("Card 3: " + rank[c3]); </code></pre> <p>In fact, some timing tests I did using a generalised (slower) form of <a href="http://docs.google.com/leaf?id=0B6Iu3YRNIHDGMzE5ODA1YmItMjQ1Mi00ZGM4LWE2NWEtYTg2OTk3YzI5OTY2&hl=en_GB&authkey=CP-A1ekP" rel="nofollow noreferrer">this algorithm</a> vs <a href="http://docs.google.com/leaf?id=0B6Iu3YRNIHDGYTBkODRiNzktZDllNC00MTRkLWI1NTAtNzdjZDQ3ZmU2ZDhh&hl=en_GB&authkey=CJaok94K" rel="nofollow noreferrer">Collections.shuffle</a> (screen shot <a href="http://picasaweb.google.com/lh/photo/Yg12_zYMBELOP2_qBpWFFg?feat=directlink" rel="nofollow noreferrer">here</a>) show that this method is <strong>about 3.7 times faster for 3 cards</strong>, and in practice <strong>faster for choosing up to 24</strong> random cards.</p> <p>To explain the algorithm to those doubting:</p> <h1>Probabilities</h1> <p>We pick random numbers - first, one of 52. If we were to remove that card then pick another, that would be one of 51...so we're ok with the random number range of the indexes we choose.</p> <p>If we were picking and removing from an array, then we just take out item at index 1, then take out item at index 2, and the same for index 3.</p> <p>What I'm doing above is adjusting the indexes to have the same effect as taking the items out of the array.</p> <p>For index two, we have a number that could be any number from 0 to 50. But, lets pretend we took out the card at index 6...</p> <p>This means that instead of a random number spread over the range 0 to 50, we now want one equally spread over the range 0-5, and 7-51. That is still a total of 51 possibilities. We do that by adding 1 to our second index, if it is >= 6. Now we have a number over the correct range with the correct distribution and equal probability if hitting any of the allowed indexes.</p> <p>The same slightly more complex logic goes for the third card: there are two spots 'missing' in the deck - so we adjust the third index to cover the available ranges. First, if it's equal to or above the first missing position, shift it up. Then if it's equal to or above the second, shift it up again. This does not bias the selection toward higher values - all we are doing is avoiding the indexes that have already been used.</p> <p>There is no skew in the probabilities.</p> <h1>Efficiency</h1> <p>It was mentioned in comments, that this algorithm and the one using <code>Collections.shuffle</code> have the same complexity (i.e., O(n)), and this method is slightly less readable. The first point to make is that this algorithm is <em>more</em> complex; i.e. to shuffle the whole array it is O(n^2). For low n, this algorithm is more efficient. And, I think the difference in <em>efficiency</em> warrants the sacrifice in readability. Compare:</p> <p><strong>Collections.shuffle</strong></p> <ol> <li>pick random number</li> <li>remove item from list</li> <li>insert item into list</li> <li>repeat 51 more times</li> </ol> <p><strong>This method</strong></p> <ol> <li>pick random number</li> <li>pick random number</li> <li>pick random number</li> <li>Up to 3 increments</li> </ol> <p>This ignores the translation from an array to a Container necessary when using the first method. The inevitable conclusion being that this method is significantly more efficient.</p> <p><em>BTW - you can visualise the O(n^2) nature when you think about picking 4 cards - which requires up to 6 increments...5 cards, up to 10...6 cards, up 15...for n, (n^2 - n)/2</em></p> <h1>Generalising</h1> <p>In this exaple I've used <code>Math.min</code> and <code>Math.max</code> as a simple way to sort a list of 2 items. In the generic case (i.e. selecting 'n' [1-52 inclusive] non-repeating random cards), we need to sort a list of up to 52 items. This can be done in O(n) worst case using an insertion sort, by keeping an ordered list of selected indexes. Selecting a new random index is done by </p> <ol> <li>Select a new random index, using <code>Random.nextInt(52 - selectedIndexListSize)</code></li> <li>Iterate over the sorted list, at each node incrementing our selected index if it is >= node value, stopping if it is less</li> <li>output card at the selected index in the array</li> <li>insert our selected index into the sorted list, at the point where we stopped</li> </ol> <p>It's O(n) for each selection - but given up to 52 selections, that makes it O(n^2).</p> <p>In terms of efficiency however, this algorithm is more efficient whenever m^2 < n, (or to be more precise, whenever m + (m^2-m)/2 < n) where n is 52 and m is the number of cards chosen. So this method is more efficient for picking 7 or less cards (or using the more precise calc, 9 or less), and therefore and obviously, more efficient for picking 3.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload