Алгоритм для головоломки

Question

Я работаю над игрой и изо всех сил пытаюсь получить некоторые общие функциональные возможности. Предположим, у нас есть фраза типа "puzzle game using group of words", поэтому я сгенерирую из этого возможные подмножества:

"puzzle", "game", "using", "group", "of", "words" и, чтобы добавить больше удовольствия, я также добавляю группу из двух последовательных слов (на данный момент группы из> 2 слов не допускаются ): "puzzle game", "game using", "using group", "group of", "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

Очень просто, если учесть, что между каждым словом есть небольшие невидимые «барьеры».

Например, «игра-головоломка с использованием группы слов» становится «головоломкой | игрой | с использованием | группы | слов |».Если у вас есть N слов, у вас есть N-1 барьеры.

Теперь для каждого «барьера» вы можете выбрать, будет ли барьер вверх или вниз.Если он работает, он действует как сплиттер.Если нет, то считает, что его не существует.

Примеры:

• "пазл | игра | с использованием | группы из | слов" -> "пазл", "game "," using "," group of "," words "

• " игра-головоломка с использованием | group | of | words "->" игра-головоломка с использованием "," group ","of", "words"

Для каждого «барьера» вы можете решить, будет он вверх или вниз, поэтому есть только 2 варианта.Поскольку у вас есть N-1 «барьеры», у вас есть в общей сложности 2 ^ (N-1) таких разделов

Редактировать: Argl = /

Группы ограничены только одним или двумяслова?

Answer 2

сначала разберите вашу строку на слова, пусть список слов будет 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})

РЕДАКТИРОВАТЬ : note:Это решение предполагает, что только 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

Answer 3

Взгляните на Звезды и бары .

Если у вас есть N строк (или звезд)

******

Теперь поместите N-1 баров между ними. Есть только один способ сделать это

*|*|*|*|*|*

Это одна возможность. Теперь поместите между ними N-2 баров.

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

и т.д.. Они определяют ваши разделы, если вы заменяете звезды строками. Чтобы сгенерировать все возможные способы размещения x баров между N звездами, вам просто понадобится способ создания комбинаций.