当可以将角色组合到其他角色时，如何从列表中获取所有角色组合 [英] How to get all role combinations, from a list, when roles can be combined to other roles
问题描述
上下文:考虑一个具有N个6面骰子的游戏.骰子的每一面都代表滚动:命令(COM)，科学(SCI)，工程师(ENG)，医疗(MED)，安全性(SEC)，以及未用于此问题的一面.游戏的目标是在挑战卡上使用骰子，其中列出了解决挑战所需的不同角色.例如，我的挑战卡可能需要1个COM，1个SCI和1个MED.因此，如果我掷骰子并获得1个COM，1个SCI和1个MED，则可以将它们应用于挑战卡以解决挑战.
Context: Consider a game where you have N 6-sided dice. Each side of a die represents a roll: command (COM), science (SCI), engineer (ENG), medical (MED), security (SEC), and a side not used for this problem. A goal of the game is to use the dice on challenge cards, which list different roles required to resolve the challenge. For instance, I may have a challenge card that requires 1 COM, 1 SCI, and 1 MED. So if I roll dice and get 1 COM, 1 SCI, and 1 MED, I can apply them to the challenge card to resolve the challenge.
其他规则:除了骰子角色与挑战卡要求的1:1映射外，骰子还可以通过以下方式组合以更改:
Additional Rules: Along with the 1:1 mapping of a dice roles to challenge card requirements, dice can also be combined to change their roles in the following manner:
- 2 MED可以成为1 SCI； 2 SCI可以成为1 MED.
- 2 ENG可以成为1 SEC； 2 SEC可以变成1 ENG.
- COM角色+任何其他角色都可以成为任何角色.这样COM + SEC可以成为ENG.
- 任何三个角色都可以成为不同的角色.因此COM + SEC + ENG可以成为MED.
问题:我想为挑战卡的要求生成所有可能的骰子组合的列表.例如，假设挑战卡需要1 SCI，1 ENG和1 MED.手动，我看到我需要:
Problem: I want to generate the list of all possible dice combinations for a challenge card's requirements. As an example, say a challenge card requires 1 SCI, 1 ENG, and 1 MED. By hand, I see that I'll need:
如果完成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)
if 1 SCI, 1 ENG, and 1 MED, done (A, B, C)
if 1 SCI, 1 ENG, and 2 SCI, done (A, B, D)
if 1 SCI, 1 ENG, and COM and other, done (A, B, E)
if 1 SCI, 1 ENG, and 3 other, done (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)
if 1 SCI, 2 SEC, and 1 MED, done (A, G, C)
if 1 SCI, 2 SEC, and 2 SCI, done (A, G, D)
if 1 SCI, 2 SEC, and COM and other, done (A, G, E)
if 1 SCI, 2 SEC, and 3 other, done (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)
if 1 SCI, COM and other, and 1 MED, done (A, E, C)
if 1 SCI, COM and other, and 2 SCI, done (A, E, D)
if 1 SCI, COM and other, and COM and other, done (A, E, E)
if 1 SCI, COM and other, and 3 other, done (A, E, F)
如果已完成(A，F，C)，则完成1个SCI，3个其他医学和1个医学
如果1个SCI，3个其他SCI和2个SCI已完成(A，F，D)
如果1个SCI，3个其他，COM等，则已完成(A，F，E)
如果1个SCI，3个其他和3个其他完成(A，F，F)
if 1 SCI, 3 other, and 1 MED, done (A, F, C)
if 1 SCI, 3 other, and 2 SCI, done (A, F, D)
if 1 SCI, 3 other, and COM and other, done (A, F, E)
if 1 SCI, 3 other, and 3 other, done (A, F, F)
此外，我需要将初始的1个SCI替换为2个MED，COM +其他设备以及具有相同分组的其他3个设备.
Further, I'd need to replace the initial 1 SCI with 2 MED, COM + other device, and 3 other device with the same groupings.
问题:尽管有这些示例，但我仍在努力寻找可以针对其进行编码的算法.有人可以提供一种算法，该算法可以将其他角色的交换角色合并为所有有效组合列表的一部分吗?
Question: Despite the examples, I'm struggling to derive an algorithm I can code against. Can someone offer an algorithm that can incorporate swapping roles for other roles as part of a list of all valid combinations?
推荐答案
您可以将其表示为语法.您的开始状态是名义(直接)挑战要求.您的边缘代表从该状态到另一状态的有效过渡，每个过渡都显示相反的过渡.
You can represent this as a grammar. Your starting state is the nominal (straightforward) challenge requirements. Your edges represent valid transitions from that state to another state, each one showing the inverse transition.
例如，对于您的卡(SCI，ENG，MED)，您将从三个元素的状态开始.现在，您将包括每个转换规则可达到的状态(组合):
For instance, for your card (SCI, ENG, MED), you will start with that state of three elements. You will now include states (combinations) reachable with each of your transition rules:
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
您可以将每个规则表示为一个函数.保留已达到的状态(组合)列表.将问题视为图遍历，并使用标准算法从给定的起始状态查找图的闭合.对于初学者:
You can express each of these rules as a function. Keep a list of states (combinations) already reached. Treat the problem as a graph traversal, and use the standard algorithms to find the graph's closure from your given start state. For starters:
(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个.
At each pass, you take the first item off the list, ring the changes on it with the rules, pushing any new states onto the list. You need to keep track of states you've already processed, and make a check that you don't exceed N elements in each state.
您可以按照该大纲进行工作吗?
Can you work from that outline?
这篇关于当可以将角色组合到其他角色时，如何从列表中获取所有角色组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
