益智游戏算法
我正在研究一款游戏,并且我正在努力获得一些通用功能。假设我们有一个短语像"puzzle game using group of words"
所以我生成这个可能的子集:益智游戏算法
"puzzle"
,"game"
,"using"
,"group"
,"of"
,"words"
,并添加更多的乐趣我还加两个连续的字组(现在组> 2话是不允许的):"puzzle game"
,"game using"
,"using group"
,"group of"
,"of words"
所以,现在的主要想法是ALL形成从这些子集构成原判可能的组合。请注意,在这种情况下,子集应该是一个分区。
例子:
"puzzle game", "using", "group", "of words"
"puzzle", "game", "using group", "of", "words"
...
不允许:
"puzzle game", "game using", .. (it's not a partition as "game" is repeated)
是否有任何已知的算法生成所有可能的组合?我认为这可能会花费很长时间的短语非常耗时,所以有没有其他方法可以尝试根据某些重量找到可能的最佳选项?
我不会假装得到代码(虽然那会很棒),但至少任何提示或想法在哪里看将会非常感激!
首先将您的字符串解析为单词,让单词列表为S.创建一个空的结果列表(让它为L)可能的返回值。
使用递归解决方案:设置一个当前的解决方案(初始化为空),并在每一步 - 添加可能的下一个字/双。当你用完你的话时,'当前'将是一个分区,并将其添加到列表中。
伪代码:
partitions(S,L) = partitions(S,L,{})
partitions(S,L,current):
if S is empty:
L.add current
else:
first <- S.first
second <- S.second
partitions(S-{first}-{second},L,current+{first second})
partitions(s-{first},L,current+{first})
EDIT:注:此解决方案假定只有1或2个字是每个分区是合法的。如果不是这种情况,而不是硬编码的递归调用,它将S减少1/2个字,则必须迭代1,...,S.size()的第一个单词。
无(使用堆栈和列表的ADT)递归解决方案:
partitions(S):
L <- empty_result_list()
stack <- empty_stack()
stack.push(pair(S,{}))
while (stack is not empty):
current <- stack.pop()
S <- current.first
soFar <- current.second
if S is empty:
L.add(soFar)
else:
stack.push(pair(S-{S.first}-{S.second},soFar+{S.first S.second})
stack.push(pair(S-{S.first},soFar+{S.first})
return L
如果你有N
字符串(又名星)
******
现在把它们之间N-1
吧。只有一种方法可以做到这一点
*|*|*|*|*|*
这是一种可能性。现在他们之间放置N-2
酒吧。
*|*|*|*|**
*|*|*|**|*
*|*|**|*|*
*|**|*|*|*
**|*|*|*|*
等,这些定义你的分区,如果你与你的字符串替换的星星。要生成所有可能的方式来将x
条形图显示在N
之间,您只需要一种生成组合的方法。
非常简单,如果你认为每个单词之间存在小的不可见的“障碍”。
例如,“使用词组的拼图游戏”成为“拼图游戏使用的词组”。如果你有N个词,你有N-1个障碍。
现在,对于每个“障碍”,您可以选择障碍是上升还是下降。如果它起作用,它就像一个分离器。如果不是,则认为它不存在。
实例:
“益智|游戏|使用|话|的基团” - “的基团”, “字”
> “难题”, “游戏”, “使用”,
“益智游戏使用|的| |组词” - >“益智游戏使用”,“集团”,“中”,“字”
对于每一个“屏障”,你可以决定它是否是向上或向下,所以只有2个选择。你有N-1 “的障碍”,则总共有2 ^(N-1)个这样的分区
编辑:Argl =/
仅限于一个或两个词的组?
是''拼图游戏使用“,”组合词“'合法的解决方案?或者它必须是每个分区1或2个字? – amit
嗨阿米,答案是至少目前没有。使用更高级别的单词(> 2)可以在未来添加,因此拥有通用解决方案将非常棒,尽管目前不需要。 – Dan