## Can I do better than binary search here?

4

I want to pick the top "range" of cards based upon a percentage. I have all my possible 2 card hands organized in an array in order of the strength of the hand, like so:

``````AA, KK, AKsuited, QQ, AKoff-suit ...
``````

I had been picking the top 10% of hands by multiplying the length of the card array by the percentage which would give me the index of the last card in the array. Then I would just make a copy of the sub-array:

``````Arrays.copyOfRange(cardArray, 0, 16);
``````

However, I realize now that this is incorrect because there are more possible combinations of, say, Ace King off-suit - 12 combinations (i.e. an ace of one suit and a king of another suit) than there are combinations of, say, a pair of aces - 6 combinations.

When I pick the top 10% of hands therefore I want it to be based on the top 10% of hands in proportion to the total number of 2 cards combinations - 52 choose 2 = 1326.

I thought I could have an array of integers where each index held the combined total of all the combinations up to that point (each index would correspond to a hand from the original array). So the first few indices of the array would be:

``````6, 12, 16, 22
``````

because there are 6 combinations of AA, 6 combinations of KK, 4 combinations of AKsuited, 6 combinations of QQ.

Then I could do a binary search which runs in BigOh(log n) time. In other words I could multiply the total number of combinations (1326) by the percentage, search for the first index lower than or equal to this number, and that would be the index of the original array that I need.

I wonder if there a way that I could do this in constant time instead?

2Since 1326 is not such a large number, why don't you simply precreate all tuples and store them in a sorted array? – Groo – 2011-12-22T14:06:57.443

Do you mean that I have a 2 dimensional array of length 1326 in one dimension and in the other it would have an array of the card range? So the first index would have an array of one hand "AA" and the last index would have an array containing all the hands possible. How would this data structure normally be initialized in software. I use Java, so I can either type it in as a literal - NO, construct in programatically in the constructor and make sure that I keep that object alive so I only have to do it once, or read it in from a file at the start of the program. Thanks for your comment. – Joe – 2011-12-22T14:29:08.853

I was thinking of a 1-dimensional array with all combinations sorted sequentially. There is 1326 ways to choose two cards from a 52 card deck, so simply create all combinations and sort them. – Groo – 2011-12-22T14:36:05.943

@Joe: note that there's no such thing as an accepted, say, "top 15%" of hands. There are different ways to rank starting Texas Hold'em holecards: Sklansky & Malmuth is one of the most common. You could also run every pair of cards vs any other possible pair (and you'd end up with different "top 15%") or (and it has been done), you could take billions of actually played hands and see which holecards netted which result and you'd end up with yet another result for the hypothetic "top 15%". – TacticalCoder – 2011-12-24T14:54:39.317

## Answers

3

As Groo suggested, if precomputation and memory overhead permits, it would be more efficient to create 6 copies of AA, 6 copies of KK, etc and store them into a sorted array. Then you could run your original algorithm on this properly weighted list.

This is best if the number of queries is large.

Otherwise, I don't think you can achieve constant time for each query. This is because the queries depend on the entire frequency distribution. You can't look only at a constant number of elements to and determine if it's the correct percentile.

Thanks for your answer. Right, I assumed that Groo meant to have a 2d array as I have commented under his comment. If I use the 1d solution, then the result that I have the answer to the question, what is the worst hand in this range, but I still would have to find out where that is in the original array (worst case BigOh(n) because its not sorted), so that I can specify the parameters of the method to get the sub-array. But I could well be missing something. – Joe – 2011-12-22T14:33:40.083

1

had a similar discussion here Algorithm for picking thumbed-up items As a comment to my answer (basically what you want to do with your list of cards), someone suggested a particular data structure, http://en.wikipedia.org/wiki/Fenwick_tree

Also, make sure your data structure will be able to provide efficient access to, say, the range between top 5% and 15% (not a coding-related tip though ;).