哈希函数-哈希函数映射5到7张牌的组合

Question

参考原问题:优化Poker-Monte-Carlo-Simulation的手值评估算法

我有一个5到7张卡的列表，并希望将它们的值存储在哈希表中，哈希表应该是一个32位整数数组，并直接由哈希函数值作为索引访问。关于52张牌组中大量的可能组合，我不想浪费太多的内存。

数字:

• 7-card-combinations: 133784560
• 6-card-combinations: 20358520
• 5-card-combinations: 2598960
• 总数:156.742.040可能的组合

存储1.57亿个32位整数值大约需要580MB。因此，我希望通过在数组中为不需要的值保留内存来避免增加这个数字。

那么问题是:一个哈希函数如何将每个可能的，非重复的纸牌组合映射到0到156.742.040之间的连续值，或者至少接近于它?

Answer 1

Paul Senzee有一个很棒的关于7张卡片的帖子(删除了链接，因为它坏了，现在指向一个NSFW网站)。

他的代码基本上是一堆预先计算的表，然后一个函数来查找给定的7张牌的数组索引(表示为64位数字，最低的52位表示牌):

inline unsigned index52c7(unsigned __int64 x)
{
    const unsigned short *a = (const unsigned short *)&x;
    unsigned A    = a[3],                B    = a[2],                        C    = a[1],            D   = a[0],
             bcA  = _bitcount[A],        bcB  = _bitcount[B],                bcC  = _bitcount[C],    bcD = _bitcount[D],
             mulA = _choose48x[7 - bcA], mulB = _choose32x[7 - (bcA + bcB)], mulC = _choose16x[bcD];
    return _offsets52c[bcA]                      + _table4[A] * mulA + 
           _offsets48c[ (bcA << 4)        + bcB] + _table [B] * mulB +
           _offsets32c[((bcA + bcB) << 4) + bcC] + _table [C] * mulC + 
                                                   _table [D];
}

简而言之，它是由基于完美散列的预先计算的查找表提供的一堆查找和按位操作。

如果你回去看看这个网站，你可以得到Senzee用来创建7张牌哈希的完美哈希码，并为5张和6张牌的表重复这个过程(基本上是为每个表创建一个新的index52c7.h)。

你也许可以把这三张桌子都打碎，但我还没有试过。

总共应该是~628 MB(4字节* 157 M条目)。或者，如果你想拆分它，你可以将它映射到16位数字(因为我相信大多数扑克手牌评估器只需要7,462个唯一的手牌分数)，然后从这7,462个手牌分数到你想要的任何手牌类别有一个单独的映射。那就是314 MB。

Answer 2

基于colex函数的概念有一个不同的答案。它适用于按降序排序的位集。下面是一个Python实现(两者都是递归的，因此您可以看到逻辑和迭代)。主要概念是，给定一个bitset，您总是可以计算出有多少个bitset具有相同数量的集合位，但小于(在字典学或数学意义上)给定的bitset。我是从这篇关于手同构的论文中得到这个想法的。

from math import factorial

def n_choose_k(n, k):
    return 0 if n < k else factorial(n) // (factorial(k) * factorial(n - k))

def indexset_recursive(bitset, lowest_bit=0):
    """Return number of bitsets with same number of set bits but less than
    given bitset.
    Args:
      bitset (sequence) - Sequence of set bits in descending order.
      lowest_bit (int) - Name of the lowest bit. Default = 0.
    >>> indexset_recursive([51, 50, 49, 48, 47, 46, 45])
    133784559
    >>> indexset_recursive([52, 51, 50, 49, 48, 47, 46], lowest_bit=1)
    133784559
    >>> indexset_recursive([6, 5, 4, 3, 2, 1, 0])
    0
    >>> indexset_recursive([7, 6, 5, 4, 3, 2, 1], lowest_bit=1)
    0
    """
    m = len(bitset)
    first = bitset[0] - lowest_bit
    if m == 1:
        return first
    else:
        t = n_choose_k(first, m)
        return t + indexset_recursive(bitset[1:], lowest_bit)

def indexset(bitset, lowest_bit=0):
    """Return number of bitsets with same number of set bits but less than
    given bitset.
    Args:
      bitset (sequence) - Sequence of set bits in descending order.
      lowest_bit (int) - Name of the lowest bit. Default = 0.
   >>> indexset([51, 50, 49, 48, 47, 46, 45])
    133784559
    >>> indexset([52, 51, 50, 49, 48, 47, 46], lowest_bit=1)
    133784559
    >>> indexset([6, 5, 4, 3, 2, 1, 0])
    0
    >>> indexset([7, 6, 5, 4, 3, 2, 1], lowest_bit=1)
    0
    """
    m = len(bitset)
    g = enumerate(bitset)
    return sum(n_choose_k(bit - lowest_bit, m - i) for i, bit in g)