Algorithm for puzzle game

I'm working on a game and I'm struggling to get some generic functionality. Suppose we have a phrase like "puzzle game using group of words" so I generate possible subsets from this:

"puzzle", "game", "using", "group", "of", "words" and to add more fun I also add group of two consecutive words (for now groups of > 2 words are not allowed): "puzzle game", "game using", "using group", "group of", "of words"

So now the main idea would be forming ALL possible combinations from these subsets that form the original sentence. Please note that in this case the subsets should be a partition.

Example:

"puzzle game", "using", "group", "of words"
"puzzle", "game", "using group", "of", "words"

...

Not allowed:

"puzzle game", "game using", .. (it's not a partition as "game" is repeated)

Is there any known algorithm that generates all possible combinations? I presume this can get very time consuming for longer 开发者_如何学编程phrases so are there alternatives that try to find possible best options based on some weight for example?

I don't pretend to get code (though that would be awesome) but at least any tip or ideas of where to look at would be really appreciated!

---

first parse your string into words, let the list of words be S. create an empty result list (let it be L) of possible return values.

use a recursive solution: set a current solution (initialized to empty), and at each step - add the possible next word/double to it. when you used up your words, the 'current' will be a partition, and add it to the list.

pseudocode:

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: note: this solution assumes only 1 or 2 words are legal per partition. if it is not the case, instead of the hard-coded recursive call which decreases S by 1/2 words, you will have to iterate over the 1,...,S.size() first words.

None recursive solution (using Stack and List ADTs):

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

---

Very simple if you consider that there are small invisible "barriers" between each word.

For example, "puzzle game using group of words" becomes "puzzle | game | using | group | of | words". If you have N words, you have N-1 barriers.

Now, for every "barrier", you can choose whether the barrier is up or down. If it's up, it acts as a splitter. If not, considers that it doesn't exist.

Examples :

• "puzzle | game | using | group of | words" -> "puzzle", "game", "using" , "group of", "words"

• "puzzle game using | group | of | words" -> "puzzle game using", "group", "of", "words"

For each "barrier", you can decide whether it's up or down, so there are only 2 choices. As you have N-1 "barriers" , you have a total of 2^(N-1) such partitions

Edit : Argl =/

Are the groups only limited to one or two words?

---

Take a look at Stars and bars.

If you have N strings (aka stars)

******

Now place N-1 bars between them. There's only one way to do this

*|*|*|*|*|*

This is one possibility. Now place N-2 bars between them.

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

etc. These define your partitions if you replace the stars with your strings. To generate all possible ways to put the x bars between N stars, you'll just need a way to generate combinations.