如何循环遍历例如 48 选择 5 的所有组合

Question

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

我想构建我自己的扑克牌评估器，但在特定部分遇到问题。

如果两名玩家拿到两张牌，则牌堆中还剩下 48 张牌。在德州扑克中，随后会再发 5 张可能的公共牌（称为牌面）。我想枚举/循环所有 48 个选择 5 种可能的棋盘组合，并计算玩家 A 获胜的次数和玩家 B 获胜的次数以及他们平局的时间。

我不知道如何系统地循环遍历每 5 张卡片组合。有人有什么想法吗？这些卡片表示为 Card 类的数组，但我也可以将它们表示为位集（如果这样可以加快速度）。

我正在用 Java 做这个。

非常感谢

Answer 1

（免责声明：我编写了一个非常快速的扑克牌评估器）

我想枚举/循环所有 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 张卡片
组合。

如果您确实想循环遍历每个组合，您必须知道扑克牌评估器通常是那种需要非常非常快的程序。这些程序通常可以每秒评估数亿只手（您没看错：数亿只）。

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

例如，下面的代码将通过最里面的循环 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 vs 169 查找表（“Ac Kd”、“As Kh”、“Ad Ks”等全部变成“AK offsuit”，而 C( 52,2) 可能的起手牌分为 169 种起手牌)。维基百科文章解释了如何获得 169 个非等效起手牌：

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

当您考虑一只手时，它们是不等价的，但一旦正如您第一手牌与第二手牌一样，“169 vs 169”是一个近似值（这是一个相当好的说法）。

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

Answer 2

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# 中的迭代器方法：

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;
            }
        }
    }
}