益智游戏的算法

Question

我正在开发一款游戏，并且正在努力获得一些通用功能。假设我们有一个像“puzzle game using group of Words”这样的短语，所以我从中生成可能的子集：

“puzzle”，“game” ，“using”，“group”，“of”，“words”并添加更多乐趣我还添加两个连续单词的组（目前> 2个单词的组不允许）：“益智游戏”、“游戏使用”、“使用组”、“组”, "of Words"

所以现在的主要思想是从形成原始句子的这些子集中形成所有可能的组合。请注意，在这种情况下，子集应该是一个分区。

示例：

"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)

是否有任何已知的算法可以生成所有可能的组合？我认为对于较长的短语来说这可能会非常耗时，因此是否有其他替代方案可以尝试根据某些权重找到可能的最佳选项？

我不会假装获得代码（尽管那会很棒），但至少任何关于在哪里查看的提示或想法将非常感激！

Answer 1

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

编辑：注意：此解决方案假设每个分区只有 1 或 2 个单词是合法的。如果不是这种情况，则必须迭代 1,...,S.size() 第一个单词，而不是通过硬编码的递归调用将 S 减少 1/2 个单词。

非递归解决方案（使用堆栈和列表 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

Answer 2

如果您认为每个单词之间都存在小的看不见的“障碍”，那么这很简单。

例如，“使用单词组的益智游戏”变为“益智 | 游戏 | 使用 | 单词组 | 单词”。如果你有 N 个单词，你就有 N-1 个障碍。

现在，对于每个“障碍”，您可以选择障碍是向上还是向下。如果它向上，它就充当分离器。如果不存在，则认为它不存在。

示例：

• “拼图 | 游戏 | 使用 | 一组 | 单词” -> “拼图”、“游戏”、“使用”、“一组”、“单词”

• “使用|组|单词的益智游戏”-> “益智游戏使用”，“组”，“的”，“单词”

对于每个“障碍”，你可以决定它是向上还是向下，所以只有 2 个选择。由于您有 N-1 个“障碍”，因此您总共有 2^(N-1) 个这样的分区

编辑：Argl =/

这些组是否仅限于一两个单词？

Answer 3

查看星星和条形。

如果您有 N 个字符串（又名星星），

******

现在在它们之间放置 N-1 个条。只有一种方法可以做到这一点

*|*|*|*|*|*

这是一种可能性。现在在它们之间放置 N-2 条。

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

等等。如果您用字符串替换星星，这些将定义您的分区。要生成将 x 条放在 N 颗星之间的所有可能方法，您只需要一种生成组合的方法。