Алгоритм нахождения оптимального количества наборов рамми-стиля?

Question

Я разрабатываю карточную игру, в которой используются наборы из трех карт в стиле рамми. Из случайного выбора карт мне нужен алгоритм, чтобы выбрать, какие карты дадут мне наибольшее количество комплектов.

Под "наборами трех в стиле рамми" я имею в виду:

• Все три карты имеют одинаковое значение, как три валета. OR
• Все три карты одной масти и последовательного порядка, например, 7, 8, 9 алмазов.

Например, с учетом карт: 6D, 7D, 7C, 7H, 8D, 8C, 9C, 10H
Я мог бы сформировать набор: {7D, 7C, 7H}, но это был бы единственный набор, который я бы выбрал, и он не был бы оптимальным.
Оптимальными наборами в этом случае являются: {{6D, 7D, 8D}, {7C, 8C, 9C}}

Я пробовал грубую силу (переставьте все данные карты, посмотрите, что соответствует порядку в этой перестановке), но это оказалось слишком медленно. Проблема в том, что она имеет сходство с другими решенными проблемами, и поэтому я спрашиваю здесь.

Answer 1

если у вас есть N карт (N = 8), вы можете перечислить все различные тройки в наборе по времени N * (N - 1) * (N - 2) (при N = 8 вы получите 336). Это довольно быстро. Проверьте, какие из троек являются наборами в стиле «рамми», и сохраните их в таблице в виде целых троек (целое число обозначает порядковые номера карточек).

Это первый шаг. Второй шаг - сделать комбинаторную оптимизацию и рассчитать оптимальный выбор. Самый простой способ сделать это - использовать поиск с возвратом. Вы запускаете индекс ('i') для множества найденных троек. Сначала вы пытаетесь включить «i» тройку в решение, а затем рекурсивно продолжить с индекса i + 1; затем вы возвращаетесь и решаете, что в решении i-я тройка равна , а не , и продолжаете с i + 1 рекурсивно. Есть много оптимизаций для этого, но для небольших наборов это будет работать довольно хорошо.

Вот как это работает с вашим примером:

Карты: 6D, 7D, 7C, 7H, 8D, 8C, 9C, 10H

Давайте перечислим все возможные тройки:

Cards        Index triple
6D 7D 8D     <0, 1, 4>
7D 7C 7H     <1, 2, 3>
7C 8C 9C     <2, 5, 6>

Полный обратный поиск выглядит так:

Decide on <0, 1, 4>:
  <0, 1, 4> INCLUDED:
     <1, 2, 3> CLASHES with <0, 1, 4>
     Decide on <2, 5, 6>:
       <2, 5, 6> INCLUDED:
          Solution with 2 sets (* BEST SOLUTION)
       <2, 5, 6> EXCLUDED:
          Solution with 1 sets
  <0, 1, 4> EXCLUDED:
     Decide on <1, 2, 3>:
        <1, 2, 3> INCLUDED:
           <2, 5, 6> CLASHES with <1, 2, 3>
           Solution with 1 sets
        <1, 2, 3> EXCLUDED:
           Decide on <2, 5, 6>:
             <2, 5, 6> INCLUDED:
                Solution with 1 set
             <2, 5, 6> EXCLUDED:
                Solution with 0 sets

Затем вы выбираете решение с большинством наборов (отмечены звездочкой).

Это довольно просто реализовать. Попробуйте!

Answer 2

Чтобы найти все возможные действительные тройки, вы можете сделать 2 шага:

1. sort cards first ascending by number, then by suit, as you did
   in your example and look what triples you can get
2. now sort a second time, but first by suit and then by number 
   and look what triples you can get

In step 1) you can just look sequencially for 3 same numbers => O(n)
In step 2) the same, but now looking for 3 sequential numbers of the same suit. => O(n)

Слияние двух результатов дает вам все возможные тройки. Если я не ошибаюсь, в этот момент вы достигли сложной задачи: максимальная комплектация , поскольку вы хотите получить максимальное подмножество неперекрывающихся троек. Поскольку количество карт ограничено и не так велико, вы можете использовать, например, алгоритм обратного отслеживания, упомянутый antti.huima для решения этой проблемы.

Answer 3

Мой интуитивный подход заключается в том, чтобы начать с обнаружения всех возможных наборов, изучения каждой карты и поиска того, что можно сделать набором с этой картой (т. Е. Последовательных вещей и вещей одинаковой ценности). Как только вы получите все возможные наборы, которые должны быть довольно быстрыми, если у вас нет действительно большого количества карт, тогда вы можете составить карту, наборы которой исключают включение других наборов (они используют те же карты). В этот момент, даже переставляя все допустимые комбинации наборов (для каждого из наборов, которых у меня нет; попробуйте добавить его, если я смогу легально использовать его в моем текущем наборе наборов; повторить), должны быть достаточно быстрыми для обслуживания.