Вычисление всех возможностей для строки с дополнительными частями

Question

Я хочу создать список всех возможных комбинаций строки, содержащей необязательные части. Это, вероятно, лучше всего объяснить на некоторых примерах:

• A[B] → A и AB
• A[B][C] → A, AB, ACи ABC
• A[B[C]] → A, AB и ABC

Надеюсь, это достаточно объясняет то, что я пытаюсь сделать.

Я мог бы взломать мой собственный маленький парсер или «алгоритм» для этого, но у меня есть сильное ощущение, что для этого есть существующее (и более простое) решение. Поскольку у меня нет никакого вида обучения CS (пока), я понятия не имею, какой алгоритм я ищу или даже какие поисковые термины использовать.

Правильно ли мое предположение и есть лина самом деле существующий (хорошо документированный) подход к этому?

Answer 1

Грамматика, которую вы определили, содержит только 2 различных объекта: терминалы (символ) или необязательная часть грамматики.

В приведенном ниже коде на Haskell это отражено в определении дискриминируемого объединения Grammar.

Первая задача - преобразовать данный конкретный синтаксис (например, «A [B]») в список частей грамматики (каждый терминал или дополнительный). В приведенном ниже коде функция fromString делает именно это.

Интересная часть, тем не менее, состоит в том, как генерировать все возможные строки для данного синтаксиса. В приведенном ниже коде функция generate делает это рекурсивно.

• Для пустого списка грамматики (который является концом рекурсии), вывод представляет собой одну пустую строку.

• Если в списке грамматик в заданной позиции обнаружен конечный символ, соответствующий символ вставляется перед всеми вариантами, сгенерированными из оставшейся части списка грамматики.

• Если в списке грамматик найдена необязательная часть, список оставшейся части списка грамматик выводится дважды;один раз с добавленной дополнительной частью и один раз без.

Для нефункциональных людей, читающих это, следует отметить, что fmap - это функция, которая отображает список в другой список. (стихийно). Другая функция, которую я использовал в приведенном ниже коде, на которую могут наткнуться не-хаскелеры, это concat, которая превращает список списков в список.

data Grammar = Terminal Char | Optional [Grammar] deriving (Show,Eq)

fromString :: String -> [Grammar] -> ([Grammar],String)
fromString [] acc = (acc,"")
fromString ('[':cs) acc = 
    let (o,rest) = fromString cs [] in
        fromString rest (acc ++ [Optional o])
fromString (']':cs) acc = (acc,cs)
fromString (c:cs) acc = fromString cs (acc ++ [Terminal c])

generate :: [Grammar] -> [String]
generate [] = [""]
generate ((Terminal c) : parts) = fmap (\s -> c : s) $ generate parts
generate ((Optional gs) : parts) = tails ++ (concat . fmap prependOpts $ tails)
    where 
        tails = generate parts
        opts = generate gs
        prependOpts :: String -> [String]
        prependOpts tail = fmap (\o -> o ++ tail) $ opts

Собираем все вместе в REPL (интерактивная оболочка)), запустив fromString "A[B][C]" [], например, приводит к:
([Terminal 'A',Optional [Terminal 'B'],Optional [Terminal 'C']],"")

И если мы запустим generate в приведенном выше списке грамматики (первая часть кортежа), мы получим все наши строки:
generate (fst $ fromString "A[B][C]" [])
["A","AC","AB","ABC"]

Answer 2

Алгоритм может быть следующим:

- Parse the string and make a rooted binary tree that on each node breaks on 
the new bracket exists or not.

- You can go through the root to the leaf of the tree.
  All paths from the root to leaves generate all combinations.

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

Answer 3

Вот что-то в JavaScript, протестировано только для трех приведенных примеров. Надеемся, что (попытка) повторения ясна из кода:

function f(string, index, combinations){
  if (index == string.length)
    return [combinations, index]
    
  if (string[index] == "["){
    let prefixes = []
    let [suffixes, nextIndex] = f(string, index + 1, [""])

    for (let combination of combinations)
      for (let suffix of suffixes)
        prefixes.push(combination + suffix)

    if (nextIndex == string.length)
      return [combinations.concat(prefixes), nextIndex]
    else
      return f(string, nextIndex, combinations.concat(prefixes))
    
  } else if (string[index] == "]"){
    return [combinations, index + 1]
    
  } else {
    for (let i=0; i<combinations.length; i++)
      combinations[i] += string[index]
    return f(string, index + 1, combinations)
  }
}

strings = [
  "A[B]",
  "A[B][C]",
  "A[B[C]]"
]

for (let string of strings)
  console.log(JSON.stringify(f(string, 0, [""])[0]))

Answer 4

Я не читал статью, но кажется, что этот вопрос изучен. Есть страница статьи 117: «Перечисление формальных языков» http://www.eatcs.org/images/bulletin/beatcs89.pdf

Вы можете найти больше по этой теме, выполнив поиск с хорошими ключевыми словами, такими как «перечислить язык для DFA»