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

Question

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

Под «наборами Рамми стиле из трех» я имею в виду:

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

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

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

Answer 1

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

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

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

карты: 6D, 7D, 7С, 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

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

Answer 3

Чтобы найти все возможные действительные тройки, вы могли бы сделать 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) 

Объединение двух результатов дает все возможные тройки. Если я не ошибаюсь, на данный момент вы достигли NP-жесткой проблемы maximum set packing, так как вы хотите получить максимальное подмножество неперекрывающихся троек. Поскольку количество карт ограничено и не так высоко, вы можете использовать, например, алгоритм обратного отслеживания, о котором упоминалось antti.huima для решения этой проблемы.