如何遍历所有组合,例如48选择5

Question

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

我想建立自己的扑克手评估员,但我遇到了特定部分的问题.

如果两名牌手获得两张牌,那么将会有48张牌.在Texas Hold'em中,再发出5张可能的社区牌(这称为牌局).我想枚举/循环所有48个选择5个可能的棋盘组合,并计算玩家A获胜的时间和玩家B获胜的时间以及他们的时间.

我不确定如何系统地循环每5张卡组合.有没有人有任何想法？这些卡表示为类卡的数组,但如果它使它更快,我也可以将它们表示为bitset.

我在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张卡组合.

如果你真的想要通过每个组合循环,你必须知道扑克手评估者通常是那种需要非常非常快的程序.这些程序通常可以每秒评估数亿手(您正确阅读:数亿).

当你需要这种高性能的"数字运算"时,你可以忘记"设计模式"和"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++) {
                        ...
                    }
                }
            }
        }
    }

这可能是一个非常糟糕的想法:通过使用查找表,你会更快.

但是对于翻牌前的三名球员(使用翻牌前桌面是不切实际的,有太多的对位),你可能想要使用五个嵌套的循环(当然,你需要使用i,j,k,l,m从剩下的46张牌中获得正确的5张牌.然后,一旦你获得了5张牌,你就可以使用一个快速的手牌评估器,它可以给你7个中最好的(5个棋盘+每个玩家的2个).

关于查找表:

大多数人使用近似的169对169查询表("Ac Kd","As Kh","Ad Ks"等等都变为"AK offsuit"并且C(52,2)可能的起手变成169类型起手).维基百科的文章解释了如何获得169个非等效的起手牌:

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

当你考虑到一只手时,它们是不相等的,但只要你用手1对手2,"169 vs 169"就是近似值(这是一个非常好的说法).

当然你可以变得更加漂亮.只有C(52,2)(它给出1326)真正不同的德州扑克起手牌,这意味着在现代计算机上构建完美的查找表(完全没有近似值)是非常实用的(C(1326,2)ain)如果你真的需要完美的数字,那就太大了.如果你可以接近逼近,那就选择169 vs 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();
    }
}

使用Iterator方法在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;
            }
        }
    }
}