Как получить все комбинации ролей из списка, когда роли можно комбинировать с другими ролями - PullRequest
Новая
       31

Как получить все комбинации ролей из списка, когда роли можно комбинировать с другими ролями

0 голосов
/ 24 мая 2019

Контекст : рассмотрим игру, в которой у вас N шестигранных кубиков. Каждая сторона кубика представляет бросок: команда (COM), наука (SCI), инженер (ENG), медицина (MED), безопасность (SEC) и сторона, не используемая для этой проблемы. Цель игры - использовать кубики на карточках испытаний, в которых перечислены различные роли, необходимые для решения задачи. Например, у меня может быть карта вызова, которая требует 1 COM, 1 SCI и 1 MED. Поэтому, если я кидаю кости и получаю 1 COM, 1 SCI и 1 MED, я могу применить их к карте вызова, чтобы решить проблему.

Дополнительные правила : Наряду с отображением ролей костей 1: 1 для вызова требований карты, кости также можно комбинировать для изменения их ролей следующим образом:

  1. 2 MED может стать 1 SCI; 2 SCI могут стать 1 MED.
  2. 2 ENG может стать 1 СЕК; 2 SEC может стать 1 ENG.
  3. Роль COM + любая другая роль может стать любой ролью. Таким образом, COM + SEC может стать ENG.
  4. Любые три роли могут стать разными. Таким образом, COM + SEC + ENG может стать MED.

Задача : Я хочу сгенерировать список всех возможных комбинаций игральных костей для требований карты вызова. Например, скажем, карта вызова требует 1 SCI, 1 ENG и 1 MED. От руки вижу, что мне понадобится:

, если 1 SCI, 1 ENG и 1 MED, выполнено (A, B, C)
если 1 SCI, 1 ENG и 2 SCI, сделано (A, B, D)
если 1 SCI, 1 ENG, и COM и другое, сделано (A, B, E)
если 1 SCI, 1 ENG и 3 других, сделано (A, B, F)

, если 1 SCI, 2 SEC и 1 MED, выполнено (A, G, C)
если 1 SCI, 2 SEC и 2 SCI, сделано (A, G, D)
если 1 SCI, 2 SEC, COM и другое, сделано (A, G, E)
если 1 SCI, 2 SEC и 3 других, сделано (A, G, F)

если 1 SCI, COM и другие, и 1 MED, сделано (A, E, C)
если 1 SCI, COM и другие, и 2 SCI, сделано (A, E, D)
если 1 SCI, COM и другие, и COM и другие, сделано (A, E, E)
если 1 SCI, COM и другие, и 3 других, сделано (A, E, F)

если 1 SCI, 3 других и 1 MED, выполнено (A, F, C)
если 1 SCI, 3 других и 2 SCI, сделано (A, F, D)
если 1 SCI, 3 другие, и COM и другие, сделано (A, F, E)
если 1 SCI, 3 других и 3 других, сделано (A, F, F)

Кроме того, мне нужно заменить исходный 1 SCI на 2 MED, COM + другое устройство и 3 других устройства с такими же группировками.

Вопрос : Несмотря на примеры, я изо всех сил пытаюсь найти алгоритм, против которого я могу кодировать. Может ли кто-нибудь предложить алгоритм, который может включать в себя обмен ролями на другие роли как часть списка всех допустимых комбинаций?

1 Ответ

1 голос
/ 24 мая 2019

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

Например, для вашей карты (SCI, ENG, MED) вы начнете с этого состояния из трех элементов.Теперь вы будете включать состояния (комбинации), доступные для каждого из ваших правил перехода: 

SCI => [MED, MED]
MED => [SCI, SCI]
b => [COM, a] for any (a, b), where a != b
d => [a, b, c] for any (a, b, c, d) where a, b, c, != d

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

(SCI, ENG, MED)
apply rule 1
(ENG, MED^3) push this to your `search` list
apply rule 2
(SCI^3, ENG) push this to your `search` list
apply rule 3 to "SCI"
(a, COM, ENG, MED) for all `a` != "SCI"; push these ...

Видите, куда это идет?

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

Можете ли вы работать с этим контуром?

...