益智游戏算法

我正在研究一款游戏，并且我正在努力获得一些通用功能。假设我们有一个短语像"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)

是否有任何已知的算法生成所有可能的组合？我认为这可能会花费很长时间的短语非常耗时，所以有没有其他方法可以尝试根据某些重量找到可能的最佳选项？

我不会假装得到代码（虽然那会很棒），但至少任何提示或想法在哪里看将会非常感激！

来源

2011-08-08 Dan

是''拼图游戏使用“，”组合词“'合法的解决方案？或者它必须是每个分区1或2个字？ – amit

嗨阿米，答案是至少目前没有。使用更高级别的单词（> 2）可以在未来添加，因此拥有通用解决方案将非常棒，尽管目前不需要。 – Dan

首先将您的字符串解析为单词，让单词列表为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

来源

2011-08-08 14:22:20 amit

谢谢阿米特，非常感谢。说实话，我宁愿远离递归，因为可能的堆栈溢出（我打算在堆栈大小可能有问题的平台上执行） – Dan

@Dan：任何递归都可以转换为堆栈+循环。一个动态分配的堆栈[而不是调用堆栈]是一个很好的解决方案吗？ – amit

当然，任何可以在堆上分配的ADT都可以。 – Dan

看看Stars and bars。

如果你有N字符串（又名星）

******

现在把它们之间N-1吧。只有一种方法可以做到这一点

*|*|*|*|*|*

这是一种可能性。现在他们之间放置N-2酒吧。

*|*|*|*|** 
*|*|*|**|* 
*|*|**|*|* 
*|**|*|*|* 
**|*|*|*|*

等，这些定义你的分区，如果你与你的字符串替换的星星。要生成所有可能的方式来将x条形图显示在N之间，您只需要一种生成组合的方法。

来源

2011-08-08 14:22:57 tskuzzy

放置N-3酒吧给出了一个可能的解决方案：*** | * | * | * [这是无效的，最大'星'之间酒吧是2]。另外，我不认为OP需要的数量，但实际的可能性。 – amit

OP要求所有组合，而不是所有组合，其中条间的最大星数为2.您可以使用此方法非常轻松地生成实际组合。我在答案的底部提到了这一点。 – tskuzzy

谢谢tskuzzy。对不起，不清楚这一点，但最初的想法是使用大小不超过2的子集。无论如何，我认为你的想法可以被限制使这项工作。谢谢你的参考，看起来很整洁。 – Dan

非常简单，如果你认为每个单词之间存在小的不可见的“障碍”。

例如，“使用词组的拼图游戏”成为“拼图游戏使用的词组”。如果你有N个词，你有N-1个障碍。

现在，对于每个“障碍”，您可以选择障碍是上升还是下降。如果它起作用，它就像一个分离器。如果不是，则认为它不存在。

实例：

“益智|游戏|使用|话|的基团” - “的基团”， “字”
“益智游戏使用|的| |组词” - >“益智游戏使用”，“集团”，“中”，“字”

对于每一个“屏障”，你可以决定它是否是向上或向下，所以只有2个选择。你有N-1 “的障碍”，则总共有2 ^（N-1）个这样的分区

编辑：Argl =/

仅限于一个或两个词的组？

来源

2011-08-08 14:28:01 Fezvez

我认为OP需要实际的可能性。也障碍之间的最大词是2. – amit

是的非斯维兹，这些团体最多只能有两个词。对不起，我的问题没有更明确。 – Dan

益智游戏算法

回答

相关问题