10

可能重复:
如何在java中从一组大小为n的集合中迭代生成k个元素子集?

我想建立自己的扑克手评估器,但在某个特定部分遇到了麻烦。

如果两名玩家拿到两张牌,那么牌组中将剩下 48 张牌。在德州扑克中,随后会发另外 5 张可能的公共牌(这称为棋盘)。我想枚举/循环遍历所有 48 种选择 5 种可能的棋盘组合,并计算玩家 A 获胜的次数、玩家 B 获胜的次数以及他们平局的时间。

我不确定如何系统地循环遍历每 5 张卡片组合。有没有人有任何想法?这些卡片被表示为一个卡片类的数组,但如果这样可以加快速度,我也可以将它们表示为一个位集。

我正在用 Java 做这个。

非常感谢

4

2 回答 2

17

(免责声明:我写了一个非常快速的扑克手评估器)

我想枚举/循环遍历所有 48 种选择 5 种可能的棋盘组合,并计算玩家 A 获胜的次数、玩家 B 获胜的次数以及他们平局的时间。

您不想在每次翻牌前两名玩家之间的对局时评估 C(48,5) (1 712 304) 手牌:大多数程序只是在两名玩家翻牌前所有可能的对局之间使用预先计算的查找表。

例如,假设您有“Ac Ad”与“7c 6c”,您只需查看包含以下内容的查找表:(1 333 573, 371 831, 6900 其中 1 333 573 是“Ac Ad”获胜的次数,371 831 是次数“ 7c 6c" 获胜,6 900 是平局数(总和为 1 712 304)。要获得一些空间,您可以丢弃 6 900,知道平局数应始终为C(48,5) - (获胜1 + 获胜 2)

(有关此答案末尾的查找表的更多信息)

但要回答你的问题:

我不确定如何系统地循环遍历每 5 张卡片组合。

如果你真的想在每个组合中循环,你必须知道扑克手评估器通常是那种需要非常非常快的程序。这些程序通常每秒可以评估数亿手(你没看错:数亿)。

当您需要如此高性能的“数字运算”时,您可以忘记“设计模式”和“OO”。你想要的是原始速度。

例如,以下将通过最内层循环 C(48,5) 次,并且速度非常快:

    for ( int i = 0; i < n; i++ ) {
        for ( int j = i + 1; j < n; j++ ) {
            for ( int k = j + 1; k < n; k++ ) {
                for (int l = k + 1; l < n; l++) {
                    for (int m = l + 1; m < n; m++) {
                        ...
                    }
                }
            }
        }
    }

再一次,对于两名玩家来说,翻牌前这可能是一个非常糟糕的主意:使用查找表会更快。

但是对于翻牌前的三名玩家(使用翻牌前牌桌不切实际,有太多对局),你可能想要像这样循环,在 C(46,5) 手牌上,使用五个嵌套循环(当然你需要使用 i,j,k,l,m 从剩下的 46 张卡片中取出正确的 5 张卡片)。然后,一旦你得到了 5 张牌,你就可以使用一个快速的手牌评估器,它会给你 7 张牌中最好的(棋盘上的 5 张 + 每个玩家的两张)。

关于查找表:

大多数人使用近似 169 对 169 的查找表(“Ac Kd”、“As Kh”、“Ad Ks”等都变成“AK 非同花”,而 C(52,2) 可能的起手牌被归为 169 类型起手)。维基百科的文章解释了如何获得 169 个非等值起手牌:

http://en.wikipedia.org/wiki/Texas_hold_%27em_starting_hands

当您考虑一只手时,它们是不等价的,但是一旦您将手 1 与手 2进行比较,“169 与 169”就是一个近似值(一个很好的说法)。

当然,你可以变得更漂亮。只有 C(52,2)(给出 1326)真正不同的德州扑克起手牌,这意味着在现代计算机上构建一个完美的查找表(根本没有近似值)非常实用(C(1326,2) ain不是那么大)如果你真的需要完美的数字。如果您可以接受近似值,请选择 169 vs 169 表(它需要 C(169,2) 或 14 196 个条目)。

于 2011-12-04T22:50:09.770 回答
16
  1. 将数组 ( A) 初始化为前 5 个索引。(0,1,2,3,4)
  2. 将 A 中最后一个可能的索引移动到下一个位置。A[k]++
  3. 将以下索引移动到以下连续位置。( A[k+1] = A[k] + 1, ...)。如果某个索引变得太大,请在步骤 2 中尝试使用较早的索引。
  4. 在 中的当前索引处生成元素A
  5. 如果可能,从第 2 步开始重复。

实现为迭代器:

public class CombinationIterator<T>
        implements Iterable<List<T>>,
                   Iterator<List<T>> {
    private List<T> items;
    private int choose;
    private boolean started;
    private boolean finished;
    private int[] current;

    public CombinationIterator(List<T> items, int choose) {
        if (items == null || items.size() == 0) {
            throw new IllegalArgumentException("items");
        }
        if (choose <= 0 || choose > items.size()) {
            throw new IllegalArgumentException("choose");
        }
        this.items = items;
        this.choose = choose;
        this.finished = false;
    }

    public Iterator<List<T>> iterator() {
        return this;
    }

    public boolean hasNext() {
        return !finished;
    }

    public List<T> next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        if (current == null) {
            current = new int[choose];
            for (int i = 0; i < choose; i++) {
                current[i] = i;
            }
        }

        List<T> result = new ArrayList<T>(choose);
        for (int i = 0; i < choose; i++) {
            result.add(items.get(current[i]));
        }

        int n = items.size();
        finished = true;
        for (int i = choose - 1; i >= 0; i--) {
            if (current[i] < n - choose + i) {
                current[i]++;
                for (int j = i + 1; j < choose; j++) {
                    current[j] = current[i] - i + j;
                }
                finished = false;
                break;
            }
        }

        return result;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

在 C# 中等效,使用 Iterator 方法:

public IEnumerable<IList<T>> Combinations<T>(IEnumerable<T> items, int choose)
{
    if (items == null) throw new ArgumentNullException("items");

    var itemsList = items.ToList();
    int n = itemsList.Count;

    if (n < 1) throw new ArgumentException("Must contain at least one item.", "items");
    if (choose <= 0 || choose >= n) throw new ArgumentOutOfRangeException("choose");

    var indices = Enumerable.Range(0, choose).ToArray();

    bool moreWork = true;
    while (moreWork)
    {
        yield return indices.Select(i => itemsList[i]).ToList();

        moreWork = false;
        for (int i = choose - 1; i >= 0; i--)
        {
            if (indices[i] < n - choose + i)
            {
                indices[i]++;
                for (int j = i + 1; j < choose; j++)
                {
                    indices[j] = indices[i] - i + j;
                }
                moreWork = true;
                break;
            }
        }
    }
}
于 2011-12-04T14:53:50.170 回答