Представьте 5-карточную покерную комбинацию

Колода карт 52. Рука состоит из 5 карт из 52 (не может иметь дубликат).

Какое наименьшее количество бит для представления комбинации из 5 карт и как?
Рука НЕ ​​зависит от порядка (KQ = QK). 64329 = 96432

Да, можно использовать 52 бита. Это может представлять собой руку любого количества карт.

Учитывая, что в руке есть ровно 5 карт, есть способ представить ее менее чем с 52 битами.

Одна карта может быть представлена ​​с 6 битами = 64. Поэтому можно просто использовать 6 бит * 5 карт = 30 бит. Но это будет зависеть от порядка. Я мог бы просто разобраться, и это должно работать. Если это не сработает, пожалуйста, дайте мне знать.

Есть ли способ получить ключ до 32 бит или меньше и не нужно сортировать 5-карточный кортеж.

Это для покерных симуляций, и сортировка будет очень затратной по сравнению с простой генерацией руки. Если у меня есть словарь с относительным значением каждой руки, это два простых поиска и сравнение для сравнения значения двух рук. Если мне нужно сначала отсортировать руки, то это большой по сравнению с двумя поисками и сравнением. В симуляции будут сравнивать миллионы. Я не получу отсортированные руки от симуляции. Сортировка не проста, как 52 51 50 49 48 до 52 51 50 49 47. Вы можете иметь стрит-флеш-четверки ....

Есть 2598960 возможных комбинаций из 5 карт. Это количество строк. Ключ 5 карт. Я хотел бы получить ключ, который является 32-битным или ниже, где карты не должны быть отсортированы в первую очередь.

Нельзя просто заказать список, так как много рук связывают. Костюм это лопата, клуб, алмаз и сердце. 7c 8c 2d 3d 4s = 7s 8s 2c 3c 4h. Существует большое количество связей.

Следующим шагом будет 64 бита, и он примет удар по виду, а не удвоит размер ключа.

Я проверил и SortedSet<int> quickSort = new SortedSet<int>() { i, j, k, m, n };удвоил время операции, но я все еще могу это сделать.

Это становится все более сложным. Я должен быть в состоянии представить лодку как двое за пятеркой (22255). Таким образом, сортировка их ломает это. Я знаю, что вы собираетесь сказать, но это быстро. Да, это быстро и тривиально, но мне нужно как можно быстрее.

C # для принятого ответа:

private int[] DeckXOR = new int[] {0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
                                    0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
                                    0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
                                    0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
                                    0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
                                    0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
                                    0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
                                    0x04878b06,0x069b3c05,0x054089a3};
public void PokerProB()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    HashSet<int> cardsXOR = new HashSet<int>();
    int cardXOR;
    int counter = 0;
    for (int i = 51; i >= 4; i--)
    {
        for (int j = i - 1; j >= 3; j--)
        {
            for (int k = j - 1; k >= 2; k--)
            {
                for (int m = k - 1; m >= 1; m--)
                {
                    for (int n = m - 1; n >= 0; n--)
                    {
                        counter++;
                        cardXOR = DeckXOR[i] ^ DeckXOR[j] ^ DeckXOR[k] ^ DeckXOR[m] ^ DeckXOR[n];
                        if (!cardsXOR.Add(cardXOR))
                            Debug.WriteLine("problem");
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("Count {0} millisec {1} ", counter.ToString("N0"), sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}

Пусть будет код. Матрица проверки на четность представляет собой матрицу размером в , так что минимальное количество столбцов, XOR которых обращается в нуль, равно . Обозначим столбца через . Мы можем идентифицировать каждый как двоичное число длиной бит. Обещание состоит в том, что XOR любого от до из этих чисел никогда не будет . Используя это, вы можете закодировать вашу руку как , где$C$$[52,25,11]$$C$$27 \times 52$$11$$52$$A_1,\ldots,A_{52}$$A_i$$27$$1$$10$$0$$a,b,c,d,e$$A_a \oplus A_b \oplus A_c \oplus A_d \oplus A_e$$\oplus$это XOR. Действительно, ясно, что это не зависит от порядка, и если две руки сталкиваются, то XOR при двух значениях хеша дает чисел, XOR которых равен нулю.$H_1,H_2$$10-2|H_1 \cap H_2|\leq 10$

Боб Дженкинс описывает такой код на своем сайте , и из этого мы можем извлечь массив

0x00000001,0x00000002,0x00000004,0x00000008,0x00000010,0x00000020,0x00000040,
0x00000080,0x00000100,0x00000200,0x00000400,0x00000800,0x00001000,0x00002000,
0x00004000,0x00008000,0x00010000,0x00020000,0x00040000,0x00080000,0x00100000,
0x00200000,0x00400000,0x00800000,0x01000000,0x02000000,0x04000000,0x07fe0000,
0x07c1f000,0x0639cc00,0x01b5aa00,0x056b5600,0x04ed6900,0x039ad500,0x0717c280,
0x049b9240,0x00dd0cc0,0x06c823c0,0x07a3ef20,0x002a72e0,0x01191f10,0x02c55870,
0x007bbe88,0x05f1b668,0x07a23418,0x0569d998,0x032ade38,0x03cde534,0x060c076a,
0x04878b06,0x069b3c05,0x054089a3

Поскольку первые 27 векторов - это всего лишь 27 чисел веса Хэмминга 1, для проверки правильности этой конструкции достаточно рассмотреть все возможных нетривиальных комбинации последних 25 чисел, проверяя, что их значения XOR всегда имеют вес Хэмминга не менее 10. Например, самое первое число 0x07fe0000 имеет вес Хэмминга ровно 10.$2^{52-27}-1 = 2^{25}-1$

Если у нас есть набор размером , вы можете представить элемент набора, используя биты . Вы говорите, что есть 2598960 возможных 5-карточных рук. Это означает, что комбинация из 5 карт может быть представлена ​​с помощью бит. 22 бита значительно короче 30 бит.⌈ lg n ⌉ ⌈ lg 2598960 ⌉ = $n$$\lceil \lg n \rceil$$\lceil \lg 2598960 \rceil = 22$

Как работает представительство? Существуют различные варианты с различными компромиссами. Я перечислю два ниже.

Жестко закодированный словарь

В этом случае количество возможных 5-карточных комбинаций достаточно мало, чтобы вы могли просто иметь жестко запрограммированный словарь, в котором перечислены все 2598960 комбинаций, и вы представляете руку по ее индексу в словаре (представленном в двоичном виде).

Другими словами, словарь может быть отсортированным списком рук. Каждая рука представляет собой 5 кортежей карт в руке в отсортированном порядке. Вы можете найти руку в словаре с помощью бинарного поиска и найти соответствующий ему индекс; и учитывая индекс, вы можете найти соответствующую руку. Или вы можете сохранить словарь в виде хеш-карты, которая отображается от руки до ее индекса. Индекс представляет собой целое число от 0 до 2598959, поэтому его можно представить с использованием 23 битов.

Этот подход будет работать и будет очень простым для программирования, но он расточителен (размер исполняемого файла программы).

Рейтинг / unranking

В качестве альтернативы, если вы заботитесь, есть лучшие методы. Смотрите, например, любую из следующих ссылок:

• https://en.wikipedia.org/wiki/Combinatorial_number_system

• Ист Сайд, Вест Сайд . Конспект лекций, Герберт С. Уилф, 14 августа 1999 г. Разделы 3.7-3.8.

• https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/

• /programming//q/3143142/781723

Общая тема известна как «ранжирование (и отсутствие рейтинга) комбинаций». Они немного сложнее в реализации и понимании, но избегают необходимости включать в программу жестко закодированный словарь.

Вы можете сортировать пять элементов и одновременно проверять наличие дубликатов без каких-либо сравнений на некоторых процессорах: предположим, что процессор имеет быструю инструкцию, которая определяет позицию набора старшего бита, и быструю инструкцию, вычисляющую число только с установленным n-м битом ,

Пусть бит (п) число с точно п-го набора бит. Пусть наибольший_бит (х) будет номером старшего бита, установленного в числе х, с неопределенным значением, если х = 0. Пусть х ^ у будет исключающим-или х и у.

Даны пять чисел a, b, c, d и e, каждое от 0 до 51, представляющих пять карт в руке.

Пусть х = битовый (а) ^ бит (б) ^ бит (с) ^ бит (г) ^ битовую (е).

Пусть A = самый высокий_бит (x), измените x на x ^ bit (A).

Пусть B = самый высокий_бит (x), измените x на x ^ bit (B).

Пусть C = самый высокий_бит (x), измените x на x ^ bit (C).

Пусть D = самый высокий_бит (x), измените x на x ^ bit (D).

Пусть E = самый высокий_бит (х).

Если х = 0, то были дубликаты в numbes а, б, в, г, е. В противном случае используйте A * bit (24) + B * bit (18) + C * bit (12) + D * bit (6) + E в качестве кодировки руки, где A, B, C, D и E определяется как указано выше. Это кодирует руку как 30-битную строку, при этом сортировка выполняется очень эффективно.